texts:
Consider a DAG of $N$ nodes, where each node can take on one of two value, either false, $0$ or true, $1$. Additionally, let each non-leaf nodes (nodes with parents) be assigned a type: either an AND node or an OR node.

Under this setting, I define a notion of a feasible state. A state is a feasible if and only if:

for every AND node in the true state, all of its parents are in the true state.
for every OR node in the true state, at least one of its parents are also in the true state.

(Note that a state can still be feasible even if some AND node is false but all of its parents are true.)

As an example, consider the following DAG. Grey nodes are leaf nodes (nodes 1 and 2), orange nodes are OR nodes (node 3), and red nodes are AND nodes (nodes 4,5, and 6). Note that nodes 4 and 5 can be classified as either AND nodes or OR nodes since they only have one parent.

There are 18 feasible states of this DAG if I counted right, as seen below. Nodes with a dark interior are true; nodes with a white interior are false.

Question: My question is, given a DAG with AND-OR nodes, what is the expression for the total number of feasible states?


texts: Find all polygons from a set that overlap a given polygon (convex case)

texts:
Problem:  Given a set of $N$ non-overlapping convex polygons $\{S_i | 1\leq i\leq N\}$ defined by their vertex coordinates $(x,y)$ and a convex polygon $P$, also defined by its vertex coordinates, find all polygons $S_i$ that overlap with $P$.  Assume an algorithm to test whether a pair of polygons overlap already exists.

Constraints:  We are allowed to perform operations of $O(N \log N)$ on $\{S_i\}$ without knowledge of $P$ (initialization step).  After that, given an arbitrary $P$ the algorithm should perform in approximately $O(\log N)$ time when $S$ consists of polygons of uniform size.  Hence, an algorithm that just tests $P$ against every $S_i$ will be rejected.

Solution idea:  On initialization, insert all vertices of the polygons of $\{S_i\}$ into a kd-tree $K$ and associate each vertex with its associated polygon.  Store the diameter $dS$ of the largest polygon in $\{S_i\}$.  Then given a polygon $P$, calculate the diameter $dP$ of $P$.  Find all vertices in $K$ that are no farther than $\max(dS,dP)/2$ (?) from any vertex in $P$.  Test $P$ against only faces that contain the vertices in $K$.

Since lookup in $K$ is a $\log(N)$ operation, then if $N$ is large and $dP$ is approximately equal to dS then the number of tests should be $<< N$.

Any other solution ideas?  Google is yielding nothing of value.

Similar to How to find polygons overlap reign but with additional constraints.


texts: Is there a linear-time algorithm to determine if an array has duplicate entries that uses only constant extra space?

texts:
Determining whether or not an array has duplicate entries has two straightforward solutions:

Build a hashset of entries, then search for elements in this hashset. This takes $\mathcal O(n)$ time and $\mathcal O(n)$ extra space.
Sort the array, then search for consecutive elements that are the same. This takes $\mathcal O(n \log n)$ time and $\mathcal O(1)$ extra space.

Is there an algorithm that can solve this problem with the best of both approaches, using only $\mathcal O(n)$ time and $\mathcal O(1)$ extra space?

Question Finding duplicate in immutable array in linear time and constant space is similar, but the solution to that question only works when the values come from the set $\{1, ..., n\}$; my values are large integers. Also unlike that question, I allow the input array to be modified and used as a workspace.

One strategy might be to attempt to turn the array into a kind of hashtable. However, this seems like it won't work because of the lack of empty space (which makes both moving objects into place hard, as well as getting $\mathcal O(1)$ queries.).

However, I suspect that this cannot actually be done, but I'm not sure how to go about proving it.


texts: Finding a Hamiltonian path in this graph family

texts:
Given a directed graph $G = (V, E)$, you have been told that a Hamiltonian path $p_0p_1\ldots p_V$ exists with the property that for each edge $p_ip_j$ that is not part of the Hamiltonian path, $i > j$.

Find any Hamiltonian path.

It is not too hard to find an $O(|V||E|)$ solution to this problem: for every vertex with out-degree one, try starting a BFS from this vertex. If ever there is more than one vertex that could be expanded next in the BFS, give up and try another vertex.

I am not necessarily looking for a more efficient solution than this (though that would be nice), but I'm having trouble finding literature on this type of graph (in general, it seems very hard to look up literature on a family of graphs you do not know the name of).

Do you know where I can find out more about this graph family, or other graph families that involve guaranteeing the existence of a Hamiltonian path/cycle with interesting properties?


texts: Find closed loops in an undirected graph given an adjacency list

texts:
I am trying to find all the cycles in an undirected graph given the adjacency list of the vertices, with the an output of all the cycles in form of the vertices they are made up of.

For example -http://i.stack.imgur.com/Ku4fd.jpg

The example depicts the graph drawn by the adjacency list with desired cycles result

1 235
2 134
3 1245
4 235
5 134

The output from the algorithm would be

Cycles:
1 2 3
1 3 5
2 3 4
3 4 5

Note that I am not trying to find ALL possible cycles in the graph but rather all the loops. We assume for this problem that there any vertex is connected to at least 2 others

I am new to discrete maths, algorithms and graph theory, any help would be greatly appreciated.


texts: Algorithm to find the two closest elements in a BST

texts:
For example, consider an AVL tree:

Performing the two_close(T) should give back (13, 12), as they are the closest elements together. Said another way, you can take any two other elements in the tree, and their absolute difference will always be greater or equal to that of the result:

$|c_1-c_2|\leq |o_1-o_2|$, where $c_i$ are the two closest elements, and $o_i$ are any other two elements in the three.

I'm trying to think of an algorithm for this that can be done is O(log n). I can modify the nodes to store additional information, but not sure what I could use.

Specifically the algorithm, I am not sure about. Visually its evident, but algorithm wise I would like a hint.


texts: How does variance in task completion time affect makespan?

texts:
Let's say that we have a large collection of tasks $\tau_1, \tau_2, ..., \tau_n$ and a collection of identical (in terms of performance) processors $\rho_1, \rho_2, ..., \rho_m$ which operate completely in parallel. For scenarios of interest, we may assume $m \leq n$. Each $\tau_i$ takes some amount of time/cycles to complete once it is assigned to a processor $\rho_j$, and once it is assigned, it cannot be reassigned until completed (processors always eventually complete assigned tasks). Let's assume that each $\tau_i$ takes an amount of time/cycles $X_i$, not known in advance, taken from some discrete random distribution. For this question, we can even assume a simple distribution: $P(X_i = 1) = P(X_i = 5) = 1/2$, and all $X_i$ are pairwise independent. Therefore $\mu_i = 3$ and $\sigma^2 = 4$.

Suppose that, statically, at time/cycle 0, all tasks are assigned as evenly as possible to all processors, uniformly at random; so each processor $\rho_j$ is assigned $n/m$ tasks (we can just as well assume $m | n$ for the purposes of the question). We call the makespan the time/cycle at which the last processor $\rho^*$ to finish its assigned work, finishes the work it was assigned. First question:

  As a function of $m$, $n$, and the $X_i$'s, what is the makespan $M$? Specifically, what is $E[M]$? $Var[M]$?

Second question:

  Suppose $P(X_i = 2) = P(X_i = 4) = 1/2$, and all $X_i$ are pairwise independent, so $\mu_i = 3$ and $\sigma^2 = 1$. As a function of $m$, $n$, and these new $X_i$'s, what is the makespan? More interestingly, how does it compare to the answer from the first part?

Some simple thought experiments demonstrate the answer to the latter is that the makespan is longer. But how can this be quantified? I will be happy to post an example if this is either (a) controversial or (b) unclear. Depending on the success with this one, I will post a follow-up question about a dynamic assignment scheme under these same assumptions. Thanks in advance!

Analysis of an easy case: $m = 1$

If $m = 1$, then all $n$ tasks are scheduled to the same processor. The makespan $M$ is just the time to complete $n$ tasks in a complete sequential fashion. Therefore,
$$\begin{align*}
 E[M]
 &= E[X_1 + X_2 + ... + X_n] \\
 &= E[X_1] + E[X_2] + ... + E[X_n] \\
 &= \mu + \mu + ... + \mu \\
 &= n\mu
\end{align*}$$
and
$$\begin{align*}
 Var[M]
 &= Var[X_1 + X_2 + ... + X_n] \\
 &= Var[X_1] + Var[X_2] + ... + Var[X_n] \\
 &= \sigma^2 + \sigma^2 + ... + \sigma^2 \\
 &= n\sigma^2 \\
\end{align*}$$

It seems like it might be possible to use this result to answer the question for $m > 1$; we simply need to find an expression (or close approximation) for $\max(Y_1, Y_2, ..., Y_m)$ where $Y_i = X_{i\frac{n}{m} + 1} + X_{i\frac{n}{m} + 2} + ... + X_{i\frac{n}{m} + \frac{n}{m}}$, a random variable with $\mu_Y = \frac{n}{m}\mu_X$ and $\sigma_Y^2 = \frac{n}{m}\sigma_X^2$. Is this heading in the right direction?


texts:
I know that AVG Memory Access Time = Hit time + Miss Rate * Miss Penalty

If I am given the AMAT and miss rate, aswell as the latency to access memory(call this x) how do I calculate the miss penalty & / or Hit Time?

For example:

AMAT = 80 (cycles)
Miss Rate = 0.4
Memory access latency = 60 (cycles)

How do I get miss penalty from this so that I can solve for hit time?

Thanks


texts: Approximate algorithm to find the minimum score

texts:
Given $n$ variables and a function $f$ such that $f(v) = N(v) + D(v)$, where $N$ and $D$ are the subfunctions of function $f$. Function $f$, can be considered as an oracle.

Query: let $v \in P$, approximate/find the minimum value that $f$ could take over all possible configurations of $v$. For e.g., if 4 variables are given $\{x_1,x_2,x_3,x_4\}$, then if we select $v$ of size 2, that means we select a set from the PowerSet of $\{x_1,x_2,x_3,x_4\}$ of size 2 it can be {x_1,x_2} or {x_2,x_3}.

[

Max Value function $f$ can take is when $v = \phi$ (thus, size of v = 0 -> No variables selected)

Max Size of $\left | v \right | \leq \frac{3}{4} n$. Here, size represents the number of variables selected from the given $n$ variables.

Brute Force:
Enumerate all possibles elements of $PowerSet \ P$, and compute $f(v)$. Note the minimum value of $f$.

Greedy approach:
In this method, we increase the size of $v$ by 1 on each iteration.

 Greedy approach for computing minimum value of f
    Input:
        Given $n$ variables
        Function $f$
    Output:
        Approximate minimum value that $f$ takes
    Working:
     $minVal = f(v) $ where $v = \phi$
     FOR{each $i = 0 to \frac{3}{4}n $}
        FOR{each $e \in {Remaining $n-i$ variables} $}
           $u = v + \{e\} $
           $Compute $f(u)$
        ENDFOR
        Let variable $e$ gives you the minimum value when added to set $
        $newVal = f(v+\{e\})$
        IF{newVal < minVal}
            minVal = newVal
            v = v + {e}
        ELSE
            break
        ENDIF
    ENDFOR

And I believe that its not differentiable (unsure as how differentiable is defined)! Its quite close to the best feature subset selection, as adding more features might improve classification.
Question: 1)Is to come up with an approximate algorithm with a performance ratio
value?
2) For the above given Greedy algorithm what would be worst possible performance? Or is it possible to come up with a approximate bound on it in comparison to the optimal solution?


texts: Algorithm for finding the limit of unkown function

texts:
I have a case of costly calculations method like this:

Input -> Output
0 -> 8
8 -> 9
9 -> 9.5
9.5 -> 9.6
9.6 -> 9.65
9.65 -> 9.654

I use the output for the next input so this way im trying to find where the output exactly matches the input or is a tiny fraction smaller.
The goal of the algorithm is to find the smallest X=Y or X>Y where (X-Y) > 10^(-10).

However since the method for calculations is costly I'm looking for an efficient way to reduce the amount of time I'm calling the method, but still retain for example the accuracy of 10 fractional digits.

Some additional Caveats:
Output is not always increasing by increasing the Input. It might hop around the limit from both sides. Also increasing the Input value more drastically might change the value the Output approaches to which is not the desired outcome.

Since I'm posting here first time i would be glad if someone tagged this question with proper tags, since honestly i don't know which tags to use.


texts: A question about $O(T \log T)$ simulation of a TM on some input by universal turing machine

texts:
In the textbook by Arora and Barak in Chapter 1 and section 1.7 they have proved how a UTM can do simulation in $O(T \log T)$ time. I have read it and understood everything except that how the $k$th shift can cost just $O(2^k)$ time. One can read the proof for complete details but I can explain my doubt as the following problem.

Assume a TM tape divided into blocks where for $i \geq 0$ the $i$th block contains $2^i$ cells. Further, assume that the $k$th block is full i.e. all $2^k$ cells in that block have some symbol of the alphabet and for all $0 \leq i < k$, the $i$th block is empty i.e. they have no symbols. Now, we need to take first $2^{k-1}$ symbols present in $k$th block and put the left most in first block, then start putting rest of the symbols in sequence by filling first half of every $i$th block for $i < k$. One can check that we have exactly that many symbols to place in lower indices block's first half.

The book say that it can be done in $O(2^k)$ time, which I am not able to prove.


texts: Is it possible to create a CFG with succesive palindromes?

texts:
In one of my homework I am requested to find a Context-free-grammar (CFG) and a push down automaton (PDA) for the following language:

$L = \{x_1\#x_2\#...\#x_k | k \geq 2, \text{ each } x_i \in \{a, b\}^*, \text{ and for some } i \text{ and } j, x_i=x_j^\mathcal{R}\}$

My problem is that the statement

$\text{ ... and for some } i \text{ and } j, x_i=x_j^\mathcal{R}\}$,

i.e. any two pairs in the sequence must be each others reverses, forces us to make all $x_i$'s palindromes, as that is the only way any two are guaranteed reverses of each other.

If that interpretation is correct, I think the problem is impossible to solve with a Context free grammar, or not? This leads me to believe I interpreted the statement wrong and it means something else, but I can't figure out what.


texts:
I need to perform 2's complement operations on -50 - -48
From a mathematical point of view the following would be true.
-50 + 48 = -2
If I would follow the steps I would have:
I got to this result by getting the bite for 50 and 48 and then reversing
-50 = 11001101
-48 = 11001111

In 2's complement:
the bite result for 11001101 - 11001111 is - 00000010 which is 2
the decimal result for 11001101 - 11001111 is -2.

Is my logic correct?
I think I am missing something.


texts: How turing machine can be used as enumerator

texts: Currently I am studying Turing machines and I understand that a Turing machine can produce all the strings of the language accepted by that particular Turing machine. We call such a Turing machine an enumerator. I have studied the formal definition of enumerators that have no input. But I am unable to realize how a Turing machine can work as an enumerator for the language $L=\{a^nb^n:n\geq0\}$. Any help would be greatly appreciated.


texts:
I have 50 documents and im using LSH+Minhashing Jaccard and i get this results:

for bands:25 -> false positives: 200
for bands:10 -> false positives: 80
for bands:2 -> false positives: 28
for bands:1 -> false positives: 4

Can anyone explain me why im getting more false positives for bigger number of bands and while decrease bands im getting less false positives?


texts: Generating symbol matrices that satisfy regular expressions row- and column-wise

texts:
I have a program that fills a matrix of size N with characters such that all words formed by each row satisfy one regular expression, and all the words formed by each column satisfies a second one.

For example, say I have $N=3$, regular expression $c^*ab^*$ for rows and $b^*ac^*$ for columns. A solution would be

$\qquad\displaystyle\begin{pmatrix}
  a & b & b \\
  c & a & b \\
  c & c & a
\end{pmatrix}$

I'm trying to find an algorithm that is faster than the brute force one. I am further looking for a way to split this algorithm in independent processes so I can use parallelism to decrease the time needed to reach a solution.


texts: References for the computational complexity of training neural networks

texts:
I'm looking for a good review paper or book chapter that offers an accessible introduction to the computational complexity of training neural networks for classification problems.

In particular, I'm trying to study questions like:

How is training complexity related to network topology ?
How is training complexity related to the complexity of the decision boundary?


texts: Create Shortest Path tree for every node after Floyd Warshall in O(nm)

texts:
Right now I am stuck with the problem, how all shortest path trees can be created in O(n*m) given G = (V,E,c) with negative and positive costs without negative cycles and n =|V| m = |E| after execution of Floyd Warshall. We were asked to think about why this is not $O(n(n+m))$ and for which graphs we really would have to do $O(n^2)$ work and if it really is $O(n^2)$ for these graphs.
The Output should be all shortest paths trees $T_v$ for any $v \in V$
I can clearly see running DFS on every node as start node and checking if an edge is part of the shortest path or not results in O(n(n+m)) which doesnt give the desired result.
I came up with the following ideas:

I thought about if I can state that n >= m/2 if we exclude all isolated nodes in $O(n)$ first, so $O(n^2) = O(nm)$ what would result in $O(nm)$ over all.
Another possibility regarding DFS would be adding edges for other trees which hold the same edge. I came up to use a $nxm$ Matrix wheter a node was added or not and keep track of visited nodes to add edges for every node. But since I have to go through all nodes every time and check for matrix entry, which does not improve that much over all.
I also thought about path construction using a next matrix, which can be created during floyd warshall though I have to do it for every combination of two nodes in two for loops and every one recursive call is worst case $O(n)$ which results in $O(n^3)$. It would get better only if a can skip loops and edges though I can´t see an efficient way to achieve this.

Do you see any flaws within in my statements above and might any of these possibilites leed to the disired outcome? How can it be solved?


texts: What is an example of a decidable language?

texts: I know that if a language is regular or context free, the language is decidable. However, if a language is decidable does that imply that it is also regular or context free?


texts: how can i find the Maximum Degree of Concurrency?

texts:
i'm studying Parallel Processing ,

and i'm confused how can i calculate the max number of concurrency in a given dependency graph ?

i know that the maximum number of concurrency is the largest number of
concurrent tasks at any point of the execution , but i can't calculate it from the graph

can someone explain how can i find the solution from the following graph ?

thank you ALL


texts:
I'm studying elementary data structures like Linked List, Doubly Linked List and Binary Trees like Binary Search Trees.

Both runs in worst case O(n) in the same operations,  so why don't we use only one data structure?


texts: Cook completeness of a variant of Vertex Cover

texts:
Is this variant of Vertex Cover Cook-complete for $\mathrm{NP}$?

Input: An undirected graph $G(V, E)$ together with a vertex cover $C\subseteq V$

Output: YES if there exists a vertex cover $C'\subseteq V$ such that $|C'|=|C|-1$, NO otherwise


texts: Build LL(1) parsing table for grammar S -> iSeS | iS | a

texts:
Task

Bulid parsing table for grammar S -> iSeS | iS | a
Resolve conflicts in this table and simulate parser work for word iiaea

Problem

I know how to make a parsing table for unambiguous grammar, and how to simulate parser. However this grammar is an example of dangling else problem.

What I tried

I was tought that I should remove left recursion and left factoring. Then make a table using first and follow. Whatever I tried I got two grammar expressions in the same row of table. Please provide me some hint what to do in this situation.

After left factorization

S ->  iSS' |a
S'-> e S | ε

Because we will never use S' ->  ε (there are no other values which can give us e in the Table except Table[S'][e] ) we can remove this production from parsing table.

Final solution


texts: Prim's Minimum Spanning Tree implementation $O(mn)$ or $O(m+n \log n)$?

texts:
I am reading Prim's MST for the first time and wanted to implement the fast version of it .

$m$ - The number of edges in the graph

$n$ - The number of vertices in the graph

Here's the algorithm :

1) Create a Min Heap of size $V$ where $V$ is the number of vertices in the given graph. Every node of min heap contains vertex number and key value of the vertex.

2) Initialize Min Heap with first vertex as root (the key value assigned to first vertex is $0$ ). The key value assigned to all other vertices is $\infty$ .

3) While Min Heap is not empty, do following

…..a) Extract the min value node from Min Heap. Let the extracted vertex be u.

…..b) For every adjacent vertex $v$ of $u$, check if $v$ is in Min Heap (not yet included in MST). If $v$ is in Min Heap and its key value is more than weight of $u-v$, then update the key value of $v$ as weight of $u-v$.

Now my point is during implementation ( I am doing in C++) in step 3(b) I have to check whether the vertex is there in the heap or not . As we know , searching in a heap is done in $O(n)$ time . So in the main while loop which will run ( $n$ number of times ) although extract-min is $O(\log n)$ but the search ( whether $v$ is min heap or not takes time proportional to size of the heap ( although it is decreasing in each step ) .

So is it correct to say that the above algorithm is $O(m+n\log n)$


texts: Does any one know what this problem is called?

texts: We are given finite sets $A$ and $B$ and a set $S\subseteq \mathcal{P}(A)$. The members of $\mathcal{S}$ may have arbitrary intersections with one another and their union is not necessarily $A$.  We wish to determine whether there is a function $A\to B$  so that no member of $B$ is the image of more than $k$ members of any $T\in S$.


texts: How are system calls handled in a virtual machine?

texts:
Quoting wikipedia, a system call is:

  In computing, a system call is how a program requests a service from
  an operating system's kernel. This may include hardware related
  services (e.g. accessing the hard disk), creating and executing new
  processes, and communicating with integral kernel services (like
  scheduling). System calls provide an essential interface between a
  process and the operating system.

In ordinary operating systems, when a system call is made the operating system enters kernel mode and performs the requested operation.

What happens to a system call made by a process in a virtual machine? Is it handled by the virtual machine only, or is it delegated to the outer kernel to be operated by the hardware-facing kernel?


texts: One rational interval function and one irrational, will they ever collide?

texts:
This question may be a little mathy or hardware-y, so I may have to ask elsewhere.

I've recently learned that if a is a positive rational number and b is a positive irrational number, there exists no common multiple between the two.

A common design consideration in threaded or embedded systems is concurrency control, when two functions or threads share resources.

So if function A runs every sqrt(2) seconds, and function B runs every 1 second, they will never run at the same time.

Is it somehow possible to use very accurate measured numbers, to make this possible? Or is it possible using exact/symbolic programs/tools? Or is it not possible at all in machine/computer computational formats?!


texts: Prof Knuth's MIX computer - Card Reader and illegal characters

texts:
I'm reading through Knuth's "The Art of Computer Programming" volume 1 (3rd edition), with the goal of understanding the complete workings of his hypothetical MIX computer in order to implement MIX in software.  Needless to say this is a long term project!  (I'm not in college or anything, just an amateur CS enthusiast doing this for fun, I have no Professors to ask!)

In Section 1.3.1 (onwards) of "The Art of Computer Programming" Prof Knuth describes in detail his MIX computer and its IO devices such as Tape, Drum and Card Readers.  The main Text does not describe the "bootstrapping" process for this machine, but Exercice 26 does.

There is one particularly onerous limitation of the Card Reader described in Exercise 26 -- that is certain characters are not allowed to be written to or read from Cards.

To me this is an important point because if this "illegal characters" limitation does apply to the MIX proper, then I cannot see any easy way to write a MIX program by hand without constantly stumbling over illegal characters.  The CMPx operators are explicitly forbidden by Ex 26 for instance.

If I was to attempt to implement MIX myself in software I would find it very convenient to ignore this "illegal characters" limit and just indiscriminately accept all characters without error.  Although in my mind this gives me some doubt as to whether my implementation would be "compliant" with Prof Knuth's MIX spec.  Accepting "illegal" characters would also make creating a MIXAL assembler a lot easier.

Questions:

Am I to understand that concepts discussed in the Exercises are not formally part of the MIX specification?
It seems arbitrary to add such a tricky obstacle, is this rather severe limitation only supposed to be true within the scope of Exercise 26 or should it be understood that it applies to the formal specification of the MIX computer throughout the entire TAOCP book set?


texts:
Can somebody tell me what the lowest amortized cost for the increment operation of a decimal counter is?

I can show the costs are O(1) and with max amortized costs of 2 (similar to a binary counter), but is this the lowest possible value?


texts:
I want to develop a genetic program that can solve generic problems like surviving in a computer game. Since this is for fun/education I do not want to use existing libraries.

I came up with the following idea:

The input is an array of $N$ integers. The genetic program consists of up to $N$ ASTs, each of which takes input from some of the array elements and writes its output to a single specific array element.

The ASTs can be arbitrary complex and consist only of four arithmetic operators ($+$, $-$, $\times$, $/$) and can operate on constants and fixed elements of the given array (no random access).

So for $N=3$, we have three ASTs, for example:

\begin{align*}
    a[0] &= a[0] + 1\\
    a[1] &= a[0] + a[1]\\
    a[2] &= a[0] \times 123 + a[1]\,.
\end{align*}

The $N$ ASTs are executed one after another and this is repeated infinitely.

Now my question, is this Turing complete or will it fail to solve some kinds of problems common for an game AI?


texts: Number of permutations with satisfactory triangles

texts:
We are given $N$ points($N \leq 40$), where no combination of three or more points is colinear. The values of $x$ and $y$ are bounded by [$0$,$10^4$]. The problem is to find the number of permutations(mod $M$) of the points that satisfy the following properties:

We draw a triangle between the first 3 points of the permutation($p_1$, $p_2$, $p_3$) through the use of line segments
For points $4$ to $N$, we draw exactly 3 line segments from $p_i$ to 3 points $p_j$ ($j < i$), such that none of these line segments intersect with any previous line segments drawn.

I will present 3 test cases that I have generated on my own(and tested via bruteforce).
Test case 1 :
$N=4$
($0$,$0$), ($0$,$4$), ($1$,$1$), ($1$,$2$)
Output = 0 since none of the permutations work.
Test case 2:
$N=4$
($0$,$0$), ($0$,$4$), ($4$,$0$), ($1$,$1$)
Output = 24 since all of the permutations work(4!).
Test case 3 :
$N=5$
($0$,$0$), ($0$,$4$), ($4$,$0$), ($1$,$1$), ($1$,$2$)
Output = 96 since all permutations work unless the first 4 points in the permutation are ($0$,$0$), ($0$,$4$), ($1$,$1$), ($1$,$2$). 5! - 4! = 96
So far I have observed that a valid permutation is one in which you can a draw valid triangle without intersecting the sides of the previous valid triangle. However, I am not sure how to build on this idea to calculate the total number of valid permutations. My solution right now is to bruteforce every permutation and manually check for intersections.


texts: What to infer about maximum height of AVL tree from these three different formulae

texts:
I have came across following problem:

  What is the maximum height of any AVL-tree with 7 nodes?

The recurrence giving number of nodes $n$ in the AVL tree for given height $h$ is as follows:

  $n(h)=n(h-1)+n(h-2)+1$

  $n(0)=1$

  $n(1)=2$

So if we follow this recurrence, we get the height of the AVL tree with 7 nodes = 3 as follows

$n(2)=n(1)+n(0)+1=2+1+1=4$

$n(\color{red}{3})=n(2)+n(1)+1=4+2+1=7$

However I find two formulae, both listed on this page:

The first one is stricter one:

  $h < 1.475 \times log_2(n(h)) - 1.475$

According to this formula, I get

$h < 1.475 \times log_2(7)-1.475$

$h<\color{red}{2.665}$
The second one is rough estimate and it is taken from Goodrich's book:

  $h < 2 \times log_2(n(h)) + 2$

According to this formula, I get

$h < 2 \times log_2(7) + 2$

$h<\color{red}{7.61}$

So with these different answers, I don't get what should I infer. Am I doing any miscalculations? Or should I just stick to what is yielded by recurrence and ignore formulae as they are mere estimates? Or should the first formula have ceil function to give perfect answer rather than the estimates as follows?

$h \color{red}{=} \color{red}{\lceil} 1.475 \times log_2(n(h)) - 1.475 \color{red}{\rceil}$


texts: Are the following loops $O(n^2)$ complexity

texts:
I'm presented with two snippets of code, and I need to determine their time complexity. I'm pretty convinced that both of these are $O(n^2)$, but I'm not 100% sure

1.)

2.)


texts:
In lambda calculus, one can prove that two expressions compute the same function if they are equivalent under both beta reduction and eta conversion, where eta conversion consists of eta reduction,
$$
(\lambda x.A x) \to A \qquad\text{if $x$ is not free in $A$}
$$
and eta expansion,
$$
A \to (\lambda x.Ax) \qquad\text{where $x$ is not free in $A$.}
$$
Thus, while one cannot computationally check whether two expressions compute the same function, one can computationally verify a proof that they do, if someone produces a sequence of beta reductions and eta conversions that takes one expression to the other. The reason that determining equality between expressions is undecidable has to do with the need to use eta expansions as well as contractions, so you have to backtrack to search for a proof.

My first question is: is the above characterisation correct? It seems to be from what I've read, but I haven't seen it explained in exactly that way and I might have misunderstood.

My second question is, does eta conversion exist in the combinator calculus, or is there an equivalent? In other words, is there a set of formal manipulations on combinator expressions that can be used to show that two are equivalent to one another?

As a simple example, the expressions $S\,K\,K$ and $S\,K\,S$ are equivalent. (They are both the identity function.) I can show this by explicitly evaluating both of them:
$$
(S\,K\,K)\,x = (K\,x)\,(K\,x) = x,
$$
whereas
$$
(S\,K\,S)\,x = (K\,x)\,(S\,x) = x.
$$
But this involves introducing variables (i.e. moving away from "pure" SK combinator expressions), and it doesn't proceed by starting from one expression and manipulating it to convert it into the other. Is there a set of syntactic moves that can be used to show this equivalence, analogously to eta conversions in lambda calculus?


texts: What's relation between Kolmogorov complexity and pseudorandomness?

texts:
In a comment on this question, @Kaveh wondered whether the questioner really wanted to ask "is there a relation between strings with high Kolmogorov complexity and pseudorandomness?" This is not the question that was answered, in the end, but I would like to know the answer.

I understand that any pseudorandom sequence can be given a short description, by describing the program that generated it (as Travis M. points out in the question linked above).  So in one sense the sequence such a sequence does not have high Kolmogorov complexity.

On the other hand, it seems as if there's some connection between pseudorandomness and Kolmogorov complexity.  For if you didn't know the algorithm, then sequences generated by a good (passes lots of appropriate statistical tests, etc.) PRNG could not be described more briefly than by giving the sequence--on average, at least.  Right?  That's implicit in the kind of tests that good PRNGs have to pass: The tests are meant to rule out cycles and other regular patterns.  (We can also require that the PRNG be cryptographically secure, if that helps.)

Happy to be told that I'm hopelessly confused.  Just point me in the right direction.


texts: Efficient algorithm for 'unsumming' a set of sums

texts:
Given a multiset of natural numbers X, consider the set of all possible sums:

$$\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\}$$

For example, $\textrm{sums}(\left\{1,5\right\}) = \left\{0, 1, 5, 6\right\}$ while  $\textrm{sums}(\left\{1,1\right\}) = \left\{0, 1, 2\right\}$.

What is the most efficient algorithm for calculating the inverse operation (measured in terms of the size of the input set of sums)? Specifically is it possible to efficiently calculate any of the following:

Whether a given set is a valid set of sums. (For example, $\left\{0,1,2\right\}$ is valid but $\left\{0,1,3\right\}$ is not.)
A multiset that sums to the given set.
The smallest multiset that sums to the given set. (For example, $\left\{1,2\right\}$ and $\left\{1,1,1\right\}$ both sum to $\left\{0,1,2,3\right\}$ but the former is smaller.)


texts: Turing machine for $a^i b^j$ with $i \geq j$

texts:
I would have a brief question about how to construct a Turing machine that is accepting only this language:

$\qquad\displaystyle L_2 = \{a^i b^j \mid i \geq j \}$.

I can't come up with any mechanism that would preserve that there are greater or equal number of 'a's than 'b's. Could you suggest me something?


texts: How do I compute a "CRC code word" from an information word and CRC polynomial?

texts:
I have the CRC polynomial 1101, and my information word is 10001111. How do I find the CRC code word?

Disclaimer: This is an assignment problem. I'd appreciate any help, particularly solving the problem for a different polynomial and word. Most of all, I'd like an explanation of what to do here, and what a CRC code word actually is, since I don't really understand the question. Though the code word is the answer for my problem, that isn't what I'm looking for here.


texts: Can an independent set (of vertices) be a vertex cover as well?

texts:
I wanted to clarify if this is possible, so I thought about a possible vertex cover that can also serve as an independent set:

So, to clarify, am I right to say that the nodes in red are both (i) a vertex cover, and (ii) an independent set?

Edit: I was confused by the theorem that states "If G = (V,E) is a graph, then S is an independent set <-> V-S is a vertex cover." So I thought that a vertex cover and an independent set are mutually exclusive.


texts: Determine if a string is a permutation of another string efficiently

texts:
Given two strings of the same length, determine if they are permutations of each other.

I can come up with two solutions, one in O(n log n) time with O(1) extra space, and one in O(n) time with O(n) extra space, but I'm wondering if there are more efficient algorithms.

If we sort the strings in-place and compare them, we get O(n log n) time with O(1) extra space.

If we use a hashtable from character to count, we can keep track of how many of each character we have in the first string, and subtract accordingly when reading characters from the second string. That's O(n) time and O(n) extra space.

Can we do better?


texts: Insert into binary tree and keep it balanced

texts: Assuming each node stores its depth, how can I achieve this? Note that I'm not talking about a binary search tree so I shouldn't need rotations. All I want is filling the tree from left to right.


texts:
I am trying to figure out if given a connect graph with N nodes and A edges, its subgraphs are connected.

In order word: given a graph G, can I have a subgraph of G that is not connected?
Or: can a subpgraph of G not be connected?

I think the answer is no because otherwise G' is not a (sub)graph.


texts: minimizing computations for evaluating two polynomial simultaneously

texts:
I want to evaluate two polynomials $f$ and $g$ simultaneously, on the same input (in a computer program). These polynomial have only coefficients $0, 1, a , b$ and their degree is less than 700.
I want to compute $f(x)$ and $g(x)$ simultaneously as efficiently as possible. I'm looking for an algorithms that say me how to do that.

For example, let $f(x) = ax^3 + bx^2 + x$ and $g(x) = x^3 + ax^2 + bx$.
We have $f(x) =  x^2(ax + b) + x$ and $g(x) = x(x^2) + x(ax+b)$.
So we first compute $x^2$ and $ax+b$ and then use them to compute $f(x)$ and $g(x)$. Here, the optimization is evaluating $x^2$ and $ax+b$ one time for both $f$ and $g$.

Is there a algorithm that can show us how we should compute $f(x)$ and $g(x)$ in fewest computations (for a computer)?  In other words, the algorithm should receive $f$ and $g$ as input and then return an algorithm for computing them.

I guess we can use algebra( some ring theory, ideal,...) or graph theory to model this problem.


texts: Variation of Set Cover Problem: Finding a maximum-sized collection of disjoint set-covers

texts:
I have the following problem, which seems to be similar to Set Cover.

We are given a set $U$ of elements (the universe, e.g., $U=\{1,2,3,4,5\}$).
We're also given a set $S$ of subsets (e.g., $S=\{\{1\},\{2\},\{3\},\{4\},\{5\},\{1,2,5\},\{1,3,4\},\{2,3,4,5\}\}$).

The standard set cover problem asks for the minimum subset of $S$ that covers the whole universe $U$, i.e., the smallest set-cover.  In our case this would be $\{\{1\},\{2,3,4,5\}\}$.

However, I'm interested in finding a collection of set-covers where each subset from $S$ is used at most once.  I want to find the largest such collection possible, i.e., to find as many different, disjoint set-covers of $U$ as possible.  Considering our example, the three set-covers $\{\{1\},\{2,3,4,5\}\}$ and $\{\{3\},\{4\},\{1,2,5\}\}$ and $\{\{2\},\{5\},\{1,3,4\}\}$ would be the output, since each one is a set-cover of $U$ and they are pairwise disjoint (no subset from $S$ is used in more than one set-cover).

Just testing all possible combinations of set-covers is definitely not an option. I have tried using an algorithm for set cover (ILP implementation) repeatedly, eliminating all used subsets in between runs. However, I'm certain that this strategy does not actually maximize the number of all possible covers.

Edit 1: I will try to describe the size of my problem a bit better. The typical size of $U$ is about 4000. $S$ consists of about 50 subsets. Each element of $S$ covers on average about 70% of $U$. Please keep in mind that I don't want to find all subset combinations out of $S$ that cover $U$. I just want to determine the maximum number of set covers using each subset from $S$ only once (or not at all). As of now I'm guessing the maximum number of possible covers is approximately 5.


texts: Sort a list of points to form a non-self-intersecting polygon

texts: Given a list (of arbitrary length) of 2-dimensional points, is there some algorithm that I can employ to sort this list of points into an order such that line segments sequentially drawn from $p_0 \rightarrow p_1 \rightarrow \ldots \rightarrow p_{n-1} \rightarrow p_n \rightarrow p_0$ would form a non-self-intersecting polygon?


texts:
Recently, I was given a puzzle by a friend of mine, which has 6 pieces. Giddy to try it out, I took it apart without batting an eye to follow what I was removing or moving or sliding.

I've been struggling with this puzzle for over a year and a half now, and so thought I would write an algorithm that would list all the possible orientations or possibilities of pieces.

To make it more general, I numbered each piece 1 though 6. But, each piece can be rotated and placed, so I extended this to 1 through 12. So now each piece has two numbers, 1 and 12 is one piece, 2 and 11, 3 and 10, etc... Now to the root of my question:

Is it even possible to write a recursive algorithm to display all possible permutations of the 12 (6) pieces such that if piece 1 is used, 12 cannot, and so forth. Reason I ask is because if this were recursive, we wont know what we picked above (unless we keep running down in the recursion tree our last picked items) so that we can skip others.

Or, even better, would it be better to write a non recursive function?

Just as a note: I am not looking for code, per se. Pseudo code or concepts, or pointers would be so grateful and helpful.

Relevant References :

The Math behind Combinations with Restrictions

The Math behind Permutations with Restrictions

Just as a note:
Seeing as this may come up; I know the number to this solution is massive, but I've already written functions that tell me if a said permutation can even be played on the board (do certain blocks collide), if at least one block is moveable (we won't want gridlock), and if the placement of blocks conforms to the size of the puzzle enclosure. All this will, hopefully, eliminate quite a bunch, and let me try by hand the remaining games.


texts:
An AVL tree is one that satisfies the height-balance property which states that: For every position p of T, the heights of the children of p differ by at most 1.

Below is an example AVL tree. However, I've highlighted a node whose child's height would imply that their difference is not at most 1.

Can someone explain to me what I am missing?


texts: Are there other interpretations of |G| than |V|, that is |V(G)|?

texts:
This may be a basic question, but I'm hoping someone can settle this nagging doubt I'm having. I'm reading up on FPT complexity using a book by Downey and Fellows. It has some introductory examples which detail complexity in terms of $|G|$, which seems to denote $|V|$ as mentioned here.

The sections containing those examples explicitly refer to $|V(G)|$ however, so I wonder if there might be other interpretations of $|G|$ that convey some nuance in terms of complexity I'm missing, or can I safely assume that it does in fact mean $|V|$?


texts: Is there an implementation of Fast Subset Convolution?

texts:
Is there an implementation of the Fast Subset Convolution from this paper available somewhere?

Fast Subset Convolution is used for many dynamic programming FPT algorithms on tree decompositions to achieve better runtimes.


texts: How to split a context-free language into three sub-languages?

texts:
I try to split the language
$$
L = \{a^ib^j \mid i \neq 2j, i \neq 3j\}
$$
into three languages
\begin{align}
L_1 &= \{a^ib^j \mid i < 2j\} \\
L_2 &= \{a^ib^j \mid 2j < i < 3j\} \\
L_3 &= \{a^ib^j \mid i > 3j\}
\end{align}
and then use one more production $S = S_1|S_2|S_3$,
but I have no idea how to find the CFG for $L_2$.


texts: Probability that a uniformly random sequence is already sorted

texts:
Now I tried tackling this question from different perspectives (and already asked a couple of questions here and there), but perhaps only now can I formulate it well and ask you (since I have no good ideas).

Let there be $k, n \in\mathbb{Z_+}$. These are fixed.

Consider a set of $k$ integers $S=\{0, 1, 2, ... k-1\}$.

We form a sequence  $a_1, a_2, ..., a_n$ by picking numbers from $S$ at random with equal probability $1/k$.

The question is - what is the probability of that sequence to be sorted ascending, i.e. $a_1 \leq a_2 \leq ... \leq a_n$?

Case $k \to \infty$:

This allows us to assume (with probability tending to $1$) that all elements $a_1, ..., a_n$ are different. It means that only one ordering out of $n!$ possible is sorted ascending.

And since all orderings are equally likely (not sure why though), the probability of the sequence to be sorted is

$$\frac{1}{n!}.$$

Case k = 2:

Now we have zeroes and ones which come to the resulting sequence with probability $0.5$ each. So the probability of any particular n-sequence is $\frac{1}{2^n}$.

Let us count the number of possible sorted sequences:

$$0, 0, 0, \ldots, 0, 0$$
$$0, 0, 0, \ldots, 0, 1$$
$$0, 0, 0, \ldots, 1, 1$$
$$\ldots$$
$$0, 0, 1, \ldots, 1, 1$$
$$0, 1, 1, \ldots, 1, 1$$
$$1, 1, 1, \ldots, 1, 1$$

These total to $(n+1)$ possible sequences. Now again, any sequence is equally likely, so the probability of the sequence to be sorted is

$$ \frac{n+1}{2^n}. $$

Question:

I have no idea how to generalize it well for arbitrary $k, n$. Maybe we can tackle it together since my mathematical skills aren't really that high.


texts: What is the complexity of checking whether an integer $n \geq 2$ is expressible in the form $a^b$ where $a, b \in \mathbb{N}$?

texts:
I am currently studying the paper Primes is in P and have a question regarding 5 section of this paper. Line 1 of the algorithm (on page 3) requires the following operation to be performed

if (n = a^b for some natural numbers a and b), output 'composite'

I have attempted to deduce the complexity of this line and have deduced the following. Assuming $n \geq 2$, $b$ must be bounded above by $\lceil \log_2 (n) \rceil$. Thus, if there exists $a,b \in \mathbb{N}$ such that $a^b = n$ then $n^\frac{1}{b}$ must be an integer. Thus, to test whether such values of $a$ and $b$ exist, we must check whether
$$
n^\frac{1}{x}
$$
is an integer for each $2 \leq x \leq \lceil \log_2 (n) \rceil$. This requires a maximum of $\lfloor \log_2 (n) \rfloor$ operations to be performed, so the complexity of this step (according to my likely incorrect analysis) would be $O(\log_2 (n))$.

However, on page 6 of the paper it says that the complexity of this step is $O^\sim (\log^3(n))$. Why is this?

Note that this question regards the specific complexity of this operation, rather than simply verifying that it is doable in polynomial time (which was done here).


texts: Instructing operating system - Knowing it's functionalities

texts:
TL;DR: I would like to know how a programming language, the OS and drivers work together to perform a task.

I (and we all) have used various softwares/modules/packages on the top of our OS which provides us with a very simple API/GUI/CLI to perform tasks. But one question which keeps me disturbing is:

How does that software/module/package actually perform any specified action? I mean, it actually should be instructing OS to do that. So, OS should be providing procedure calls. But many functionalities aren't provided by the OS itself but the device driver provides it. So, how does the OS know what functions are supported by this particular device? And how can we instruct a particular device to perform a particular task?

Like suppose we are planning to change the IP address of a computer, we can do it through the OS's GUI or CLI. IP address is a logical thing and doesn't belong to a specific device (hardware), so we don't need any device driver for that. Keeping this simple, how can I write a module in python (without using already available API functionality) to change the IP address of a computer? Suppose the language itself i.e. python or a module/package written in python provides this functionality that calling a function such as change_ip() does the task. But how does it actually work in background? I know the background job is different for different OSes but I don't know how that module/package/language interacts with the OS. Or is it doesn't actually interact with the OS and performs the operations itself? (Maybe its possible in some cases)

Now, some other example. Suppose I would like to change the MAC address of the machine. Now, this operation is device dependent (the Network Card). Also, few NICs doesn't support this MAC changing functionality. This is actually dependent on the device driver and not the driver itself. So how can the OS know if the function is supported or not? Also, if the module/package/language is directly performing tasks without the help of OS, how can it know if the functionality is supported?

A very few might understand this question.. I don't know how to ask.. I am pursuing BE in Computer Engineering and I know several concepts and theories. But our education system makes us learn the things separately and not understand them in a combined manner. Like what would be the benefit if I know Operating System and Python but I don't know how they interact with each other and work in a combined manner. So, this is the base of my query.

I looked for an answer on Google but never found one.. Thank you..


texts: Is mapping reduction from $\overline{A_{TM}}$ possible?

texts:
I know $\overline{A_{TM}}$ is not Turing Recognizable (to prove it, infact, I proved its complement to be both Turing-recognizable and not decidable).

My question is, if $\overline{A_{TM}}$ is not Turing Recognizable, can I reduce $\overline{A_{TM}}$ to some language A (say $E_{TM}$) to show it is not Turing Recognizable, too? Or this does not makes sense, because it's not Turing Recognizable and so cannot exists such a reduction function/TM?


texts:
Consider how one would represent the following image in vector graphics:

Pretty simple, right?  The entire shape can be represented by a single path element.

But suppose additionally that you want to color the heart at the top red.  The path element is an open shape, so trying to fill it results in an appropriately red heart but also implementation-dependent bleeding between the spiral endpoints.

Obviously, one could just draw the heart and the spiral tails as separate elements, but then the vector graphics representation no longer mirrors how a human being would draw the same image, and makes it more difficult to manipulate as a single object.  One needs a way to communicate to the computer that two particular path segments within the larger path intersect in such a manner that they close a sub-shape.

Is there a vector graphics format capable of doing this?  More relevantly, how is it implemented and are there any papers on it?


texts: Is the tree shown a valid red-black tree?

texts:
I have made a red-black tree and I think that it is not valid. Could someone please verify?

As far as I know, in red-black tree we also consider the leaf nodes at the NULLS of the visible leaf nodes and these NULL nodes are considered to be black.
So, by this logic, if we consider the order root->left->left->left as black, then no. of black nodes to that NULL node are 2.
Also, if we consider the node root->right->right->right->right->right as black, then no of black nodes to that NULL node are 3.
So, according to the above argument, it should not be a valid red-black tree.
Am I right or am I missing some important concept?


texts: Assign undirected edges in a mixed graph to make graph cyclic/acyclic

texts:
What is the complexity of the following problem?

Given a mixed (some edges directed, some undirected) graph, assign a direction to all the undirected edges to make the graph contain a cycle.

It doesn't "feel" like an NP-hard problem, but I can't think of an easy poly-time algorithm.

What about to make the graph acyclic?

As R B points out in the comments, to make the graph acyclic, you can just use a topological sort on the directed edges (ignoring the undirected edges temporarily) to get an ordering of the vertices, then use that ordering to direct the undirected edges.  Therefore, that problem is easy and can be solved in $O(|V|+|E|)$ time.

However, orienting the edges to create a cycle is more tricky.
Consider the graph:

    A
  /   \
 B --> C

In this case, simply sorting the graph to get A B C and then pointing the AC and AB edges backwards does not reveal the cycle.


texts:
I am reading the paper Measuring the hardness of SAT instances by Ansótegui, Bonet, Levy and Manyà (Proc. 23rd AAAI Conf. on AI, pp. 222–228, 2008) (PDF). I am trying to understand the last part of the demonstration of the Lemma 3 (in bold). For this, I get an example. Let be $\Gamma = (a+b)(a+b')(a'+c)(a'+c')$ then its tree-like refutation is:

Following the demonstration of the last part of the Lemma 3 (in bold), $[b\rightarrow 1]\Gamma=(1)(a)(a'+c)(a'+c')$, and adding the literal $b'$ where $[b\rightarrow 1]$ has removed it, we get $\Gamma' = (1)(a+b')(a'+c)(a'+c')$. In accordance the paper the tree-like refutation of $\Gamma'$ is a proof for $\Gamma \vdash b'$. According to the paper, similarly, for $[b\rightarrow 0]$, $[b\rightarrow 0]\Gamma = (a)(a'+c)(a'+c')$, and adding the literal $b$ where $[b\rightarrow 0]$ has removed it, we get $(a+b)(a'+c)(a'+c')$. My questions are,

1) Is there any difference between these Strahlers? for me there is not any difference, but why the author consider the function $\max$?

2) From the demonstration,

  Adding a cut of $x$ to these two proofs, we get a proof of $\Gamma \vdash \Box$.

Is it a rule of sequente calculus, if yes, following wikipedia Could you help to identify who are $\Sigma$, $\Pi$, $\Delta$ and $\Sigma$?

What means cut of $x$?

  Lemma 3 The space satisfies the following three properties:

  $s(\Gamma \cup \{\Box\})$ = 0
  For any unsatisfiable formula $\Gamma$, and any partial truth assignment $\phi$, we have $s(\phi(\Gamma))\leq s(\Gamma)$.
  For any unsatisfiable formula $\Gamma$, if $\Box\notin\Gamma$, then there exists a variable $x$ and an assignment $\phi\colon\{x\}\to\{0,1\}$, such that $s(\phi(\Gamma))\leq s(\Gamma)-1$.

  The space of a formula is the minimum measure on formulas that satisfy (1), (2) and (3). In other words, we could define the space as:3

  $$s(\Gamma) = \min_{x, \overline{x}\in\Gamma, b\in\{0,1\}} \big\{
\max\{s([x\mapsto b](\Gamma))+1, s([x\mapsto\overline{b}](\Gamma))\}\;\big\}$$
  when $\Box\notin\Gamma$, and $s(\Gamma\cup\{\Box\}) = 0$.


texts: Is memorization necessary in learning computer science?

texts:
Backgrounds
Hi guys, I am now trying to teach myself some basic computer science theories. Specifically, I am using the book, CSAPP (computer systems, from a programmer’s perspective) and 15-213 taught by CMU
Question
My question is whether I need to memorize all the details covered in such theoretical courses (eg. the structure of an ELF file, the process of linking). If not, what is the methodology in approaching computer science theories.
This becomes even confusing when we have got searching engines now, considering we can always search for the facts that we need. If so, what is the purpose of learning? What shall we learn?


texts:
I am currently dealing with a problem that I believe to be a network flow related problem, and I am trying to find some similar solved problems to help me formulate my solution. I want to make it clear that I am not searching for a solution here, but asking a community of more experienced individuals if they have experience with/heard of similar problems to what I am about to describe.
Given an nxn matrix, let some small number of matrix indices (I will refer to them as nodes from now on) be colored blue, and rest of the nodes be colored white. Any white node that is adjacent (not including diagonal) to a blue node will become blue unless a block is placed between them. So for example, in a 2x2 grid, if the node at (0, 0) is blue and the rest are white, the whole grid will become blue unless blocks are placed between (0,0) and (0, 1) as well as (0, 0) and (1, 0).
Now, each block placed has a cost of 1, and each white node being converted to a blue node will have some cost greater than zero (the cost will be the same for all white nodes). The goal is to place blocks on the matrix such that the total cost is minimized.
It most problem instances, especially with a low cost of white nodes becoming blue, it will be optimal to let some white nodes suffer becoming blue. For example, going back to the 2x2 problem instance, if each white to blue conversion only costs .25, then letting all the nodes become blue will cost .75, whereas placing 2 blocks would cost 2, and so the minimum cost would be .75 and letting the blue spread across the grid.
I am wondering if anyone can recall a problem instance/algorithm that is similar to what I am attempting to solve and could suggest researching it? I have scoured the internet relating to min-cut/max-flow algorithms, but I am having trouble relating this problem to anything regarding network flow. Any suggestions of problems to research would be much appreciated.


texts:
This is a question I have stumbled upon in my exam revision and I find it intriguing:
My computer is blue and it has a massive graphics card and a DVD and every-
thing so which is more powerful: my computer or a Pushdown Automaton?

My Thoughts
When we talk about power I have assumed this to be computational power. I believe that a PDA has the computational power to equal the computational power of a CPU (cpu in this case is the core elements of a computer ie memory and processor). This is because a PDA utilises a stack which is memory(RAM) in a computer. The PDA has states as does a CPU and also the PDA calculates simple logic at each state. I realise that the PDA itself would be a complex series of states to emulate the computational power of the cpu and there would have to be a series of PDAs to compute different functions.
My Question:  I know that Turing machines are best used to simulate the logic of a CPU but am I right in saying that a PDA (Or PDA's) can be designed to be as powerful as a cpu?


texts:
Suppose that we have been given a regular expression $L$ and then we are asked to calculate the minimum number of states in the minimum sized DFA?
How can we go about solving such questions?

What I thought is that first we need to convert the given regular expression to The DFA and then minimise it.

  Is there any better way which can directly give the number of states or even the minimised DFA? The way I follow becomes sometimes very tough as it depends whether the expression at hand is an easy one or  a tough one. Is there some general algorithm or some lemma which might come in handy in order to answer such questions?

(This is supposed to be a reference question. Please include a general description of your method as well as a non-trivial example.)


texts:
A deck of cards is 52. A hand is 5 cards from the 52 (cannot have a duplicate).

What is the least amount of bits to represent a 5 card hand and how?
A hand is NOT order dependent (KQ = QK).  64329 = 96432

Yes, can use 52 bits. That can represent a hand of any number of cards.

Given a hand is exactly 5 cards is there a way to represent it with less than 52 bits.

A single card can be represented with 6 bits = 64.  So could just use 6 bits * 5 cards = 30 bits.  But that would be order dependent.  I could just sort and this should work. If that would not work please let me know.

Is there a way to get the key to 32 bits or under and not have to sort the 5 card tuple.

This is for poker simulations and sorting would be a lot of overhead compared to just generating the hand.  If I have a dictionary with the relative value of each hand it is two simple lookups and a comparison to compare the value of two hands. If I have to sort the hands first that is large compared to two lookups and a comparison.  In a simulation will compare millions.  I will not get sorted hands from the simulation.  The sort is not simple like 52 51 50 49 48 before  52 51 50 49 47.  You can have straight flush quads ....

There are 2598960 possible 5 card hands.  That is the number of rows.  The key is the 5 cards.  I would like to get a key that is 32 bits or under where the the cards do not need to be sorted first.

Cannot just order the list as many hands tie. Suit are spade, club, diamond, and heart.  7c 8c 2d 3d 4s = 7s 8s 2c 3c 4h.  There is a large number of ties.

The next step is 64 bits and will take the hit of the sort rather than double the size of the key.

I tested and SortedSet<int> quickSort = new SortedSet<int>() { i, j, k, m, n }; doubles the time of the operation but I still may do it.

It gets more complex. I need to be able to represent a boat as twos over fives (22255).  So sorting them breaks that. I know you are going to say but that is fast.  Yes it is fast and trivial but I need as fast as possible.

C# for the accepted answer:

private int[] DeckXOR = new int[] {0x00000001,0x00000002,0x00000004,0x00000008,0x00000010,0x00000020,0x00000040,
                                    0x00000080,0x00000100,0x00000200,0x00000400,0x00000800,0x00001000,0x00002000,
                                    0x00004000,0x00008000,0x00010000,0x00020000,0x00040000,0x00080000,0x00100000,
                                    0x00200000,0x00400000,0x00800000,0x01000000,0x02000000,0x04000000,0x07fe0000,
                                    0x07c1f000,0x0639cc00,0x01b5aa00,0x056b5600,0x04ed6900,0x039ad500,0x0717c280,
                                    0x049b9240,0x00dd0cc0,0x06c823c0,0x07a3ef20,0x002a72e0,0x01191f10,0x02c55870,
                                    0x007bbe88,0x05f1b668,0x07a23418,0x0569d998,0x032ade38,0x03cde534,0x060c076a,
                                    0x04878b06,0x069b3c05,0x054089a3};
public void PokerProB()
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    HashSet<int> cardsXOR = new HashSet<int>();
    int cardXOR;
    int counter = 0;
    for (int i = 51; i >= 4; i--)
    {
        for (int j = i - 1; j >= 3; j--)
        {
            for (int k = j - 1; k >= 2; k--)
            {
                for (int m = k - 1; m >= 1; m--)
                {
                    for (int n = m - 1; n >= 0; n--)
                    {
                        counter++;
                        cardXOR = DeckXOR[i] ^ DeckXOR[j] ^ DeckXOR[k] ^ DeckXOR[m] ^ DeckXOR[n];
                        if (!cardsXOR.Add(cardXOR))
                            Debug.WriteLine("problem");
                    }
                }
            }
        }
    }
    sw.Stop();
    Debug.WriteLine("Count {0} millisec {1} ", counter.ToString("N0"), sw.ElapsedMilliseconds.ToString("N0"));
    Debug.WriteLine("");
}


texts: Why is Combinatorial Sketching for Finite programs possible?

texts:
I was reading Combinatorial Sketching for Finite Programs and wanted to understand why synthesis of the sketching language was possible/feasible.

As far as I understand a partial program is transformed to the Quantified Boolean Formula Satisfiability Problem (QBF) and a sketched (partial) program $S$ with specification $P$ and control (i.e. wholes to fill) $c$ satisfy the following:

$$ \exists c \in \{ 0, 1 \}^k, \forall x \in \{ 0,1\}^m ; P(x) = S(x,c) $$

since the problem is decidable since $c$ and $x$ range in finite domains we can solve the above problem.

Obviously it goes without saying that this cannot work in general (otherwise we could somehow solve the halting problem...?) and I am trying to understand what exactly makes this work (since I'd potentially like to design my own sketching language and I'm trying to understand how one goes about doing that). Does it work because:

  We have a sketch of the program and a specification to match?

i.e. what is impossible to do is have a general procedure that generates sketches automatically? (otherwise we could solve the halting problem)? Is the only reason this is doable because the human is given a sketch $S$ of the program? Obviously the specification has to be given otherwise how do we know what programs to choose?


texts: Matching algorithm, match pairs: what would be the right way to do it?

texts:
How would you solve the following problem...
Theres a table filled with data like this:

Data1: 50 51 48 55 50
Data2: 51 49 52 50 51
Data3: 49 53 50 51 48
Data4: 48 50 52 51 53
Data5: 47 50 51 54 49
Data6: 50 48 50 49 52
Data7: 51 50 51 49 51
Data8: 48 51 49 50 50
...

The goal is to create pairs from the table, based on similarity of the rows.

As i learned from the comments, it is matching, thx :)

A difference bigger than 3 is not allowed.

When values are close to each other, they should be paired, for example

Data2: 51 49 52 50 51
Data7: 51 50 51 49 51

have very close values and should be a paired/grouped. So if this is our first pair, what is the next one?
And how to handle outliers (in the columns)? For example

Data1: 50 51 48 55 50

has in the fourth column the value 55. With the criteria no bigger difference than 3, the only possible companion is Data5:

Data5: 47 50 51 54 49
Data1: 50 51 48 55 50

But in cloumn 1 and 3 the delta is 3, so in the mean maybe it isnt such a good choice.

Outlier who couldnt be assigned because of the too big deviation, will not be considered.
The algorithm has not to be efficient.

Maybe you can see that it is just not clear for me, how to check the data  against each other. To match the best fitting rows together.

So to answer the question about the use: each datarow is one measured device. You need two devices for the signal reproduction. For the best reproduction result you need maximum coherence between those two. So perfect would be an ideal match. So the goal is to find the best matching devices in the table.


texts: new language accepted by FA when new transitions are added to a FA?

texts:
found this question online and I am trying to solve this question. I have solved this question but I think I might be missing some cases. Could someone verify if my answers are correct?
Let N = (Σ ∪ {λ}, Q, δ, q0, {qf }) be a λ − NFA and let L = L(N) be the language accepted by N. For N assume q0 has no incoming transitions and qf has no outgoing transitions. For each of the following FAs that are modifications of N describe the language accepted by each in terms of L.
(a) A λ-transition is added from qf to q0.
(b) Add a λ-transition from q0 to every state reachable from q0 along a path with labels that may be λ or symbols from Σ.
(c) Add a λ-transition to qf from every state that reach qf along some path.
(d) The FA where both (b) and (c) are done.

a) L+
b) For this one I have defined a function suff, this takes all the valid strings in the original Language and generates new stings from them. For example, if L = {112,12} where alphabet is {1,2}
Then, suff(L) means suff(112) + suff(12)
where suff(112) = {112,12,2}, keeps chopping off the first symbol until u get empty string
Similarly, suff(12) = {12,2}
So, the final answer would be suff(L) + the empty string. (Is this correct?)
C) for this one, I defined pre which is similar to suff but chops off the last symbol.
pre(123) = {123,12,1}
pre(112) = {112,11,1}

So, the final ans is pre(L) +  empty string
d) I need help with this one..


texts: How to find a perfect matching with this constraint?

texts:
I have a positive integer $n$ and two disjoint sets of nodes $V=\{v_1,\ldots,v_n\}$ and $W=\{w_1,\ldots,w_n\}$. I also have a weight function $f:V\times W\to\mathbb{R}_{>0}$ and a positive number $\alpha$. The function $f$ is represented by the matrix $\mathbf{F}=\left[f_{vw}\right]$ as:

$$\mathbf{F}=\begin{bmatrix}
f_{11} & \cdots & f_{1n} \\
\vdots & \ddots & \vdots \\
f_{n1} & \cdots & f_{nn} \\
\end{bmatrix}.$$

I would like to create a perfect matching between $V$ and $W$ (that is associate one node from $V$ to exactly one node from $W$) such that some constraint is satisfied (it is given explicitly next). Or, I am looking for a function $a:V\to W$ that is bijective between $V$ and $W$.

The constraint is specified by a matrix $\mathbf{G}=\left[g_{vw}\right]$ defined by: $g_{vw}=f_{va(v)},\forall v,w$. For example, if I have $n=3$, $v=\{1,2,3\}$ and $W=\{1,2,3\}$ and $\mathbf{F}$ is given by:
$$\mathbf{F}=\begin{bmatrix}
1 & 3 & 2 \\
4 & 7 & 1 \\
7 & 9 & 5 \\
\end{bmatrix},$$
and the bijection is $a(1)=2,a(2)=3,a(3)=1$. The matrix $\mathbf{G}$ will be:
$$\mathbf{G}=\begin{bmatrix}
3 & 2 & 1 \\
7 & 1 & 4 \\
9 & 5 & 7 \\
\end{bmatrix}.$$

Now, the constraint says that $\alpha\min\limits_{v}g_{vv}\geqslant\max\limits_{v\neq w}g_{vw}$. With the same example, if $\alpha=1$, the bijection $a$ does not satisfy the constraint since $\alpha\min\limits_{v}g_{vv}=1$ and there exists some $w\neq v$ such that $g_{vw}>1$.

In summary, I would like to find a bijection between $V$ and $W$, $a:V\to W$, such that
$$\alpha\min\limits_{v}g_{vv}\geqslant\max\limits_{v\neq w}g_{vw},$$
where $g_{vw}$ is defined previously.


texts: "OOD allows ADTs to be created and used."

texts:
I just had a CS mid-term and one of the questions was:

  OOD allows ADTs to be created and used.

  True
  False

I answered false, but my answer was marked as incorrect. I suspect what the question means is "objected-oriented design can be used to implement abstract data types", but if that's what it means it seems very clumsily worded to me. My rationale for answering false was ADTs are conceptual and exist outside of any particular programming paradigm, so "creation" of an ADT is purely a theoretical exercise.

To me it seems like the question is analogous to saying "OOD allows algorithms to be created". You might use OOD in the implementation of an algorithm, but it has nothing to do with its creation.

Would I be right in appealing my mark? My professor is kind of an idiot and I've already corrected him on several other points throughout the term, so I'm trying to avoid antagonizing him if I'm wrong.


texts: How LR parser works with grammar containing epsilon productions

texts:
In Dragon book  for compiler design there is this example of SDT in Example 5.16

$L\rightarrow En$
$E\rightarrow \{ print (' +') ; \} \space E_1 + T$
$E\rightarrow T$
$T\rightarrow \{ print (' *' ) ; \} \space T_1 * F$
$T\rightarrow F$
$F\rightarrow ( E )$
$F\rightarrow digit \space \{ print ( digit . lexval) ; \}$

and then it writes

Unfortunately, it is impossible to implement this SDT during either top
down or bottom-up parsing, because the parser would have to perform critical
actions, like printing instances of * or +, long before it knows whether these
symbols will appear in its input.
Using marker nonterminals $M2$ and $M4$ for the actions in productions 2
and 4, respectively, on input 3, a shift-reduce parser ( see Section 4.5.3) has
conflicts between reducing by $M2 \rightarrow \epsilon$, reducing by $M4 \rightarrow \epsilon$, and shifting the
digit.

Definition of marker:

SDT's that can be implemented during parsing can be characterized by in
troducing distinct marker nonterminals in place of each embedded action; each
marker $M$ has only one production, $M  \rightarrow  \epsilon$. If the grammar with marker non
terminals can be parsed by a given method, then the SDT can be implemented
during parsing.

But I don't see how such conflicts could occur on an input "3". Should not the LR(0) automaton
always reduce by $M_2\rightarrow \epsilon$ on a lookahead that is $digit$ instead of shifting $digit$ to stack. So there would never be shift/reduce conflict. explain please.

Edit:
-
Suppose I have a Grammar, $G'$ with following productions.
$A\rightarrow M B$
$B\rightarrow b$
$M\rightarrow \epsilon$
then the LR(0) itemset will be as follows,
$I_0:$

$S\rightarrow .A$
$A\rightarrow .MB$
$B\rightarrow .b$
$M\rightarrow .$

Now since on $b \in follow(M)$, on input "b", we could either shift it to stack and move to state having item $[B\rightarrow b.]$ or reduce by production 3. So it is a Shift/reduce conflict.


texts: DFA for the set of strings of 0’s and 1’s such that there are two 0’s separated by a number of positions that is a multiple of 4

texts:
I've being trying to understand this statement for quite a long time especially the "number of positions" part, but i can't seem to interpret it correctly.What i understand is that the statement means that there should be two 0's seperated by a number of symbols that are multiples of 4 i-e (0 , 4 , 8 , 16...), according to my understanding the string "01110", should not be in the language as the 0's are seperated by three 1's which is clearly not a multiple of 4, but the solution to the problem i've seen here:

https://www.google.com.pk/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwjxtfzov9jWAhXGJ8AKHfP6D6gQFggmMAA&url=http%3A%2F%2Fwww.ics.uci.edu%2F~goodrich%2Fteach%2Fcs162%2Fhw%2FHW1Sols.pdf&usg=AOvVaw2XrD6v28VSz30I7l5jvdLd

Suggests that "01110" is in the language.

Can someone please help me with understanding what the question statement means?


texts: Proving that a set of grammars for a given finite language is decidable

texts:
Let the language $$L = \left\{ \langle G \rangle \ |\ L(G) = \{1,\ldots , 1000\}, \text{ G is a CFG }\right\}$$

  Prove that $L \in R$.

Well, I think that for a start we need to check whether or not $L(G)$ is infinite, so we only need to check if there's a word $w\in L(G)$ such that $n \le \left|w\right|\le 2n$

Suppose $L(G)$ is finite. How can I validate that $L(G) = \{1,\ldots ,1000\}$?


texts:
i wonder: how can i find minimal distance of a self correcting code in following situation: if we know that a code can fix every 3 errors(if not more than 3 errors, the word is recovered) and can detect  every 5 errors(if between 3 and 5 errors, the algorithm will report that the error can not be fixed), how can we find its minimal distance?

i know that a code that fixes(hamming distance properties) $i$ number of errors costs a length of $2i+1$, and for detection of $i$ errors it costs a length of $i+1$. so the minimal length in this scenario is should been 7, but it cannot be 7 because distinguishing an error word E which can be obtained by discovering 5 errors or fixing 3 errors is undistinguisable in the following scenario: let a,b correct code words and E an erroronous word that can be obtained by 5 errors on the word x or by 3 errors from word y, so putting it like this makes it easier: x----E--Y, so it is not possible to distinguish between a word K that might have 3 errors or 5 errors in it, because its hamming distance from X or Y is the same. so, the minimal distance is 8.

what is the correct minimal hamming distance here?

**edit: please show me a formal and correct way to write the explanation why it cannot be 7 so i can learn correctly.


texts: Determine whether a TM visits each of its states exactly once during computation

texts:
(Decidable or not?) Formulate the following problem as a language:
  Given a Turing machine $M$ and a string $w$, determine whether $M$ visits each of its states exactly once during the computation with input string $w$. Prove your answer.

So the problem above is what I am trying to solve. I am looking for a general direction to solve this so far this is what I am thinking but I may be completely wrong.

My Thoughts: This problem is decidable because the Turing machine can have a list of all possible paths ,$E^*$, and we could check $E^*$ to ensure that each state was visited once and only visited once within the computation. However this doesn't seem like nearly enough and I am not sure what direction to head.


texts: Efficient algorithm for rectangle containment

texts:
Given a set of $n$ intervals on a line, there is a $O(n \log n)$ algorithm to find intervals which are contained in other intervals (e.g., Manber, "Using induction to design algorithms", 1988).  Is there a $O(n \log n)$ algorithm for axis-aligned rectangles in higher dimensions?

I did some search on the internet, and tried to think about it myself, but could not find a generalization for higher dimensions.  For example, given $n$ axis-aligned rectangles on the plane, the task is to find which rectangles are contained in other rectangles.


texts: Size of neighborhood in local search for symmetric TSP

texts:
I read about local search / neighborhood search methods for the symmetric TSP and I'm not quite sure about a few things.
The given example said:

  Suppose we have an instance of the symmetric TSP with n nodes and the neighborhood $N^k$.
  Here $N^k$ is the $k$-change-neighborhood (delete $k$ edges and afterwards insert $k$ other edges).

We define $\gamma_{n, k}$ to be the number of possibilities to delete $k$ non-adjacent edges in a given tour.

If I understand this correctly, it should be as follows:
$\gamma_{n, 0} = 1$, $\gamma_{n,1} = n$, $\gamma_{n, 2} = n(n - 3)$, and so on.

  Is there a formula for $\gamma_{n,k}$?


texts: Maximum flow problem with non-zero lower bound

texts:
Given $G = (V,E )$ a directed graph, if $ X \subseteq V $ we write
  $$\begin{align*}
       \delta ^{+}(X) &= \{ xy\in E \mid x \in X, y\in V - X \} \\
       \delta ^{-}(X) &= \delta ^{+}(V - X )\,.
\end{align*}$$
  $\delta^{+}(v)$  and $\delta^{-}(v)$  are short notation for $\delta^{+}(\{v\})$ and $\delta^{-}(\{v\})$.

  We call a circulation in $G$ a function $f\colon E \rightarrow \mathbb{R}$ with the property that
  $\sum _{e \in  \delta ^{+}(v) } f( e ) = \sum _{e \in  \delta ^{-}(v) } f( e )$ for any $v \in V$.
  Let  $\ell, u\colon E \rightarrow \mathcal{R}^{+}$ be two functions with the property that $\ell( e ) \leq u( e )$ for any edge $e \in E$. Demonstrate that exactly one of  the following statements is true:

  There exists a circulation $f$ in $G$ so that $\ell( e ) \leq f( e ) \leq u( e )$, for all $e \in E$.
  There exists a set $X\subseteq V$ so that $\sum _{e \in  \delta ^{+}(X) } u( e ) < \sum _{e \in  \delta ^{-}(X) }  \ell( e )$.

I tried setting the problem up as an LP problem but I don`t think that is the right way. Any help or idea is well appreciated.


texts: Is Space Complexity Always Less Than Or Equal To Time Complexity?

texts:
Background
I am working on proving a novel problem to be P-Complete, and this requires using a logspace reduction to reduce some known P-Complete problem to the novel problem. Particularly, I am reducing the Circuit Value Problem, the de facto P-Complete problem, to the novel problem.

The Experienced Difficulty
P-Complete reductions must use logarithmic space in the reduction in order to be meaningful. However, for the novel problem, it is very easy to show that the reduction takes logarithmic time, whereas it is difficult to show that it takes logarithmic space.

The Complicating Factor
There are many Q and A sites online which declare that an algorithm's space complexity is always less than its time complexity. For example: https://www.quora.com/Is-there-any-algorithm-whose-space-complexity-is-more-than-time-complexity. This is just one of many. I have scoured the literature on the subject, reading through Cook, Karp, Stockmeyer, and many more, yet I am unable to find this claim that space complexity is always less than time complexity captured in a rigorous manner. Yet this claim seems pervasive and almost treated as "common knowledge".

Why the Complication Matters
If it is true that space complexity is always less than or equal to time complexity, then instead of doing a logspace reduction, I can show that the reduction can be done in log time, which is much easier in my particular case.

What I Need
Can anyone point me to the paper which established this "common knowledge" idea that space complexity is always less than or equal to time complexity? Or a textbook or other authoritative source?

-Thank You


texts: What are some fundamental issues computer science tries to address?

texts:
I was wondering, if physics has the origins of the universe or the nature of space, time, and matter, biology has the existence of the cell and the origin of life, are there mysteries that computer science could seek to unravel?

This question does not concern the theories and technologies developed by computer science, but more existential, ontological issues.


texts: Proving that every derivation-tree has at most one leftmost-derivation in a context free grammar

texts:
I am trying to prove the following theorem:

For every derivation-tree in a context-free grammar $G=(V,T,P,S)$ there exists at most one leftmost derivation.

My partial proof by contradiction (I stucked at Cases (2) and (3)):

Let $G = (V,T,P,S)$ be a context-free grammar.

Suppose that for some derivation-tree there are two distinct rightmost derivations:

$S = _0 ⟹_{lm} _1 ⟹_{lm} _2 ⟹_{lm} … ⟹_{lm} _n = x$
$S = _0 ⟹_{lm} _1 ⟹_{lm} _2 ⟹_{lm} … ⟹_{lm} _m = x $
(x is the frontier of the tree)

It is clear that $_1 = _1$ since the first derivation uses a production rule of the form
$S ⟶ Y_1 … Y_k$ where $Y_1 … Y_k$  are the children of the root node $S$.

Now since the derivations are distinct we get that there are three cases:

(1) $∃ i_0 ∈ \{2, … , min(m, n)\}, (∀ k ∈ \{ 0, … , i0 -1 \}, _k  = _k ) ⋀  _{i_0}  ≠ _{i_0}$
(In other words: it says that the two derivations are identical till we reach some point in both derivations where they become distinct)

(2) $n < m ⋀ ∀ k ∈ \{ 0, … , n \}, _k  = _k$
(In other words: it says that the first derivation is a “sub” derivation of the second one)

(3) $n > m ⋀ ∀ k ∈ \{ 0, … , m \}, _k  = _k$
(In other words: it says that the second derivation is a “sub” derivation of the first one)

Case (1): If $∃ i0 ∈ \{2, … , min(m, n)\}, (∀ k ∈ \{ 0, … , i0 -1 \}, _k  = _k ) ⋀  _{i_0}  ≠ _{i_0}$ , We get that $∃w∈T^*, ∈(V∪T)^* , A∈V, _{i_0-1}  = _{i_0-1} = wA$ , Since both derivations are in the same derivation-tree, The only possibility is that different production rules where used on different variables, but since the derivations are leftmost-derivations, we must use at the $i_0$’th derivation the corresponding production-rule (in the derivation-tree) on $A$,  since $A$ is the leftmost variable. Again, since the derivations are in the same derivation-tree, The production rule used on A  must be the same rule $A ⟶ Z_1 … Z_k$ where $Z_1 … Z_k$  are the children nodes of the node $A$. Therefore we reached the contradiction $_{i_0}  = _{i_0}$.

Case (2): If $n < m ⋀ ∀ k ∈ \{ 0, … , n \}, _k  = _k$ then we get that $_n  = _n$ , Now  since $_n = x$ we get $_n  = _n = x$, Since m > n and since $x = _n ⟹_{lm} … ⟹_{lm} _m = x$, we get that $x  ⟹_{lm}^+  x$.

Now I do not know how to proceed.

Case (3): If $n > m ⋀ ∀ k ∈ \{ 0, … , m \}, _k  = _k$ then we get that $_m  = _m$ , Now since $_m = x$ we get $_m  = _m = x$, Since n > m and since $x = _m ⟹_{lm} … ⟹_{lm} _n = x$, we get that $x  ⟹_{lm}^+  x$.

Now I do not know how to proceed.

Maybe it got something to do with the fact that $x$ is the frontier of the derivation tree.

Thanks for any help.


texts: Is there an algorithm which finds sorted subsequences of size three in $O(n)$ time?

texts:
I want to prove or disprove the existence of an algorithm which, given an array $A$ of integers, finds three indices $i, j$ and $k$ such that $i < j < k$ and $A[i] < A[j] < A[k]$ (or finds that there is no such triple) in linear time.

This is not a homework question; I saw it on a programming forum framed as “try to implement such an algorithm.” I suspect that it is impossible after various experiments. My intuition tells me so, but that does not really count for anything.

I would like to prove it formally. How do you do it? I would ideally like to see a proof laid out step-by-step, and then if you are so inclined, some explanation of how to go about proving/disproving simple questions like this in general. If it helps, some examples:

[1,5,2,0,3] → (1,2,3)
[5,6,1,2,3] → (1,2,3)
[1,5,2,3] → (1,2,3)
[5,6,1,2,7] → (1,2,7)
[5,6,1,2,7,8] → (1,2,7)
[1,2,999,3] → (1,2,999)
[999,1,2,3] → (1,2,3)
[11,12,8,9,5,6,3,4,1,2,3] → (1,2,3)
[1,5,2,0,-5,-2,-1] → (-5,-2,-1)

I supposed that one could iterate over $A$, and each time there is an $i < j$ (our current $j$, that is), we make a new triple and push it onto an array. We continue stepping and comparing each triple until one of our triples is complete. So it's like [1,5,2,0,-5,-2,-1] → 1..2.. -5.. -2.. -1, [1,5,2,0,-5,-2,3,-1] → 1..2.. -5.. -2.. 3! But I think this is more complex than mere $\mathcal{O}(n)$ as the number of triples on our triple array would in the worst case correspond to the size of the input list.


texts:
I had a question about altering a text file. I have data in the following format.

1 a,b,c
2 d,e
3 a, l, m,n

Note that some of them have spaces after the coma

Now I have to resort the data in the following format

1 a
1 b
1 c
2 d
2 e
3 a
3 l
3 m
3 n

Now my plan is to first parse the data, and hold a count of how many data elements there are for each number. (Ex. for the number 1, there are 3 elements).
Then I would move down the data by 3 spaces, starting from the bottom. Kinda like moving an array. (The main concern here is space more than time complexity)

Then I would enter each data element at the top.

My first question is, how exactly would I parse the data in a txt file and indicate delimiters such as the coma and the possible spaces.

Second, having done this, how would I just move down a whole line inside a text file down one?

I am very sorry if my question is convoluted. I will gladly clarify anything. Thank you so much for your time! Please let me know if there is anything i need to add. Also, I'm comfortable in both java and c. So advice on either language is useful.


texts: 3SAT with an oracle for expanding the clauses

texts:
Let's consider 3SAT, so we have clauses like:

(A or B or C) and (A or not B or D) and ...

If we distribute the "and" over the first two clauses, we get the disjunction of:

      A and A --> simplifies to A

      A and not B

      A and D

      B and A

      B and not B --> simplifies to false

      B and D

      C and A

      C and not B

      C and D

I presume the brute force strategy of expanding all the clauses and simplifying when possible would take exponential time.  My question: what if an oracle gives you a certificate telling you which clauses to expand?  Is it known whether this could get you down to polynomial time?

Let's call this language 3SAT^A, so it's something like:
3SAT^A = {(x, A(x)) : x is a 3SAT formula}, where A(x) tells you how to expand the clauses in x.

Is it known whether there is an A such that 3SAT^A is in P?  If so, could one hope to show P != NP by showing that no such A is computable in polynomial time?


texts: Protecting a specific sized message with some limitations

texts:
So I make a research on my own. I have a device it allows a 64bit message. I wanted to secure it but I 64bits arent just enough to hash it and encrypt it. Is there really any good Hash function out there that can produce a 64bit result from a seed of 128bit ? I tried to search but there are many limitations.
Note I use micro controller so a lightweight one is a must "key"


texts: Complexity of a set partition derived problem

texts:
I am stuck at the complexity of the following problem:
Given a multiset $S = \{x_1,..., x_n\}$ of $n$ integers and a natural number $k$. Can $S$ be partitioned into multisets $S_1,... S_j$ such that for all $S_i \subseteq S$ there is $\sum_{ s \in S_i} s = k?$

I have found out that this may be somehow related to the EqualSubetSum Problem or the partition problem. But is this problem really $NP$-complete or exists a polynomial algorithm depending on $k$ and $n$ to decide this problem?


texts: What does it mean when $A$ is a NP-Complete Problem but $\bar{A} = NP$?

texts:
I'm still in the process of grokking computational complexity.

However, I came across a statement like the above in an old midterm paper I'm reviewing, and I'm not sure I completely follow its logic.

$NP$ is the class of solveable decision problems that can be verified in polynomial time.

So when we say that $A$ is a NP Complete problem, it is understandably contained within the $NP$ class.

However, if $\bar{A}$ is included in the class $NP$, wouldn't these two postulates essentially indicate that ALL problems are $NP$?

Any insight into how to look at this would be much appreciated!


texts:
I'm trying to find the language of the given CFG
$S \to aB \mid bA \mid a \\ A \to bAA \mid aS \\ B \to aBB \mid bS$
I understand that the productions $S \to aB, S \to bA, A \to aS$ and $B \to bS$, correspond to the language where the number of a's are equal to the number of b's, but how do I interpret the other productions? Any help is appreciated!


texts: Is there a task that is solvable in polynomial time but not verifiable in polynomial time?

texts:
A colleague of mine and I have just hit some notes of one of our professors. The notes state that there are tasks that are possible to solve in polynomial time (are in the class of PF) but that are NOT verifiable in polynomial time (are NOT in the class of NPF).

To elaborate about these classes: We get some input X and produce some output Y such that (X,Y) are in relation R representing our task. If it is possible to obtain Y for X in polynomial time, the task belongs to the class of PF. If it is possible to verify polynomial-length certificate Z that proves a tuple (X,Y) is in relation R in polynomial time, the task belongs to the class of NPF.

We are not talking about decision problems, where the answer is simply YES or NO (more formally if some string belongs to some language). For decision problems it appears that PF is a proper subset of NPF. However, for other tasks it might be different.

Do you know of a task that can be solved in polynomial time but not verified in polynomial time?


texts: Does closure under union and concatenation imply closure under Kleene star?

texts: For decidable languages (or a particular subset of decidable languages, e.g., regular, context free) does closure under Kleene star follow from the proof of closure under union and concatenation? The only thing that the latter seems not able to produce is an empty string.


texts: Context-free string that satisfies constraint?

texts:
I'm not sure on how to come up with a string that is in terms of $p$ for

$ a^ib^jc^k$  where $ i+j = k^2$

Where $p$ is the pumping length. I can't seem to find anything in terms of $p$ that satisifies the constraint. Any ideas or sugeestions are appreciated!


texts:
I'm not sure what terminology to use. Here is some input:

John  has items: A B D
Peter has items: A C D

And I want to produce such a table, that would count the # of people having these items (0-count is not required to be outputted):

A     2
B     1
C     1
D     1
A,B   1
A,C   1
A,D   1
A,B,D 1
A,C,D 1

What's the name of such a table and what sort of efficient algorithm could I use to produce it?

Functional programming style more preferable. An Excel solution would be great though I'm not sure it's doable.

It would be used to determine if there are any correlations.

Thank you.

PS here is a rudimentary example solution in Scala which isn't efficient:

scala> val items = List('A', 'B', 'C')
items: List[Char] = List(A, B, C)

scala> val people = List(List('A', 'B'), List('B', 'C'))
people: List[List[Char]] = List(List(A, B), List(B, C))

scala> val combos = (1 to items.size).view.map(items.combinations(_).map(_.toSet).toSet).flatten
combos: scala.collection.SeqView[scala.collection.immutable.Set[scala.collection.immutable.Set[Char]],Seq[_]]#Transformed[scala.collection.immutable.Set[Char]] = SeqViewMN(...)

scala> combos.map(s => s -> people.count(p => s.subsetOf(p.toSet))).toMap
res15: scala.collection.immutable.Map[scala.collection.immutable.Set[Char],Int] = Map(Set(A, C) -> 0, Set(B) -> 2, Set(A, B, C) -> 0, Set(A, B) -> 1, Set(A) -> 1, Set(C) -> 1, Set(B, C) -> 1)


texts: If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?

texts:
I'm am stuck solving the next exercise:

Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is context-free.

I know that there should exist a PDA that accepts $L$ and a DFA that accepts $R$. I'm now trying to combine these automata to a PDA that accepts the right quotient. If I can build that I proved that $L/R$ is context-free. But I'm stuck building this PDA.

This is how far I've made it:

  In the combined PDA the states are a cartesian product of the states of the seperate automata. And the edges are the edges of the DFA but only the ones for which in the future a final state of the original PDA of L can be reached. But don't know how to write it down formally.


texts: Advantages of algorithm W over algorithm J for type inference in Hindley-Milner type system

texts:
According to A modern eye on ML type inference

  Furthermore, for some
  unknown reason,
  W
  appears to have become more popular than
  J, even though the latter is viewed—with reason!—by Milner as a simplification of the former.  Jones’ presentation of type inference for
  Haskell [21] does rest upon an implementation of
  J.

Indeed, I've seen many expositions of W. But this is the first one of J that I've seen.

So does W have advantages which these notes overlook? Or is it just about avoiding mutability in Milner's presentation of J?


texts: Why solutions for Normal form Ordinary least squares and Linear Regression are different

texts:
I am trying to apply Linear Regression method for a dataset of 9 sample with around 50 features using python. I have tried different methodology for Linear Regression i.e Closed form OLS(Ordinary Least Squares), LR(Linear Regression), HR(Huber Regression), NNLS( Non negative least squares) and each of them gives different weights.

But I can get the intuition why HR and NNLS has different solution, but LR and Closed form OLS have the same objective function of minimizing the sum of the squares of the differences between observed value in the given sample and those predicted by a linear function of a set of features. Since the training set is singular, i had to use pseudoinverse to perform Closed form OLS.

$\beta ={(A^{T}A)}^{-1}A^Ty$

For LR i have used scikit-learn Linear Regression which uses lapack library from http://www.netlib.org/lapack/lug/node27.html to solve the least-squares problem

System of linear equations or a system of polynomial equations is referred as underdetermined if no of equations available are less than unknown parameters. Each unknown parameter can be counted as an available degree of freedom. Each equation presented can be applied as a constraint that restricts one degree of freedom. As a result an underdetermined system can have infinitely many solutions or no solution at all. Since in our case study, system is underdetermined and also is singular, there exists many solutions.

Now both pseudoinverse and Lapack library tries to finds minimum norm solution of an underdetermined system when no of sample is less than no of features. Then why the closed form and LR gives completely different solution of the same system of linear equations. Am i missing something here which can explain the behaviors of both ways. Like if the peudoinverse is computed in different ways like SVD, QR/LQ factorization, can they produce different solution for same set of equations?


texts: Successful applications of fuzzy logic to reasoning in AI?

texts: I've done some searching and it seems that fuzzy logic is used in (electronic) controllers. I'm interested in seeing how well it fares as a tool for reasoning. Are there any robots or programs that do clever things with it?


texts: When are two simulations not a bisimulation?

texts:
Given a labelled transition system $(S,\Lambda,\to)$, where $S$ is a set of states, $\Lambda$ is a set of labels, and $\to\subseteq S\times\Lambda\times S$ is a ternary relation. As usual, write $p \stackrel\alpha\rightarrow q$ for $(p,\alpha,q)\in\to$. The labelled transition $p\stackrel\alpha\to q$ denotes that the system in state $p$ changes state to $q$ with label $\alpha$, meaning that $\alpha$ is some observable action that causes the state change.

Now a  relation $R \subseteq S \times S$ is a called a simulation iff
$$ \forall (p,q)\in R,
   \text{ if } p \stackrel\alpha\rightarrow p'
   \text{ then } \exists q', \;
   q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R.
$$

One LTS is said to simulate another if there exists a simulation relation between them.

Similarly, a relation $R \subseteq S \times S$ is a bisimulation iff $\forall (p,q)\in R,$
$$
\begin{array}{l}
   \text{ if } p \stackrel\alpha\rightarrow p'
   \text{ then } \exists q', \;
   q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R
\text{ and } \\
\text{ if } q \stackrel\alpha\rightarrow q'
   \text{ then } \exists p', \;
   p \stackrel\alpha\rightarrow p' \text{ and } (p',q')\in R.
\end{array}
$$

Two LTSs are said to be bisimilar iff there exists a bisimulation between their state spaces.

Clearly these two notions are quite related, but they are not the same.

  Under what conditions is it the case that an LTS simulates another and vice versa, but that the two LTSs are not bisimilar?


texts: What complexity class is this set of grammars? RE?

texts:
Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$, $X \to a$, or $X \to \epsilon$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, determine whether $S$ can derive $a$.

(Thanks Yuval Filmus for pointing out this characterization - see first comment in linked question)

What complexity class does this correspond to? RE?

Related questions:

What complexity class does is this set of grammars? L-complete?

What complexity class does is this set of grammars? NL-complete?

What complexity class is this set of grammars? In between NL and P?

What complexity class is this set of grammars?