texts: Proving the (Non-)Emptiness condition for Rabin tree automata given by Pnueli and Rosner

texts:
At section 8 of the paper On the Synthesis of a Reactive Module, the authors state the following theorem:

Proposition 2 (Non-Emptiness Condition)
Let $A = (Q, \delta, Q_0, \Omega)$ be a tree automaton with
$\Omega = \{(L_i, U_i) | 1 \leq i \leq m\}$ and $|Q|=n$.
Then, $T_\omega(A) \neq \emptyset$ if and only if for some finite tree
$E$ and a run $r=(\nu, E')$ of $A$ on $E$, for every path $\pi$ in $E$,
there exist an integer $i$, $1 \leq i \leq m$, and strings
$x_0, x_1, \dots, x_{n+1}$, such that the following hold:

$x_0 \leq x_1 < \dots < x_n < x_{n+1} \in \pi \cap Ft(E)$.
For all $l$, $0 < l \leq n+1$, $\nu(x_l) \in U_i$.
For all $j$, $1 \leq j \leq m$, $\nu[x_1,x_{n+1}] \cap L_j \neq \emptyset \Rightarrow \nu[x_0, x_1] \cap L_j \neq \emptyset$.
$\nu[x_0, x_{n+1}] \cap L_i = \emptyset$.

They do not provide a proof, but add that:

The following proposition and its proof essentially consist of delicate modifications of the results reported in [HR72] as theorem 1 and its proof.

Since I could not grasp the intuition beyond the third condition, I tried to prove the theorem by myself, with the proof of the mentioned theorem in mind. Proving the 'only if' direction was easy, but I can not come up with a proof for the 'if'.
The idea in [HR72] follows these steps:

build a mapping $\eta$ from an infinite tree $T$ to the finite tree $E$
define a run $\overline{r}$ of $A$ on $T$ by means of $\eta$ and the run $r = (\nu, E')$
show that $\overline{r}$ is an accepting run for $T$, thus $T \in T_\omega(A)$

In [HR72] the conditions are different from those stated by Pnueli and Rosner and I am not able to adapt that proof to this alternative Non-Emptiness condition.
How can I adapt the proof reported in [HR72], in order to prove Proposition 2?


texts: Any option other recursive search possible to go from one 2d point to another point with fixed set of possible moves?

texts:
Problem:  Given (a,b) and (c,d), find if you can you reach from (a,b) to (c,d) if we can only have the following moves
(a, b) to either (a+b,b) or to (a,a+b).

Example (1,4) to (5,9) is possible because:  (1,4) -> (5,4) -> (5,9)

Solution:  I can think of is recursive search

Set 1: TestedPoints, initially empty
Set 2: PointsToTest, initially (a,b)

While (PointsToTest not empty):
   Remove nextPoint (x,y),
   Compare (x+y,y) with (c,d):
          If x+y=c and y=d, return TRUE
          Else if x+y < c and y < d, add (x+y,y) to PointsTotest if it is not present in TestedPoints set

   Compare (x,x+y) with (c,d):
          If x=c and x+y=d, return TRUE
          Else if x < c and x+y < d, add (x,x+y) to PointsTotest if it is not present in TestedPoints set

Is there anything faster?

if we can express the progressive X,y points in an expression, I thunk we can do faster.  For e.g: Get a as close to c as possible and b as close to d as possible using equations and then do recursive search over smaller interval.


texts: How to write recurrence relation for the following scenario?

texts:
A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function $g(x)$ for each node x. If the cost of computing $g(x)$ is min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then what is the worst case time complexity?

Since $g(x)$ is applied on the 2 halves of the binary tree, I guess the recurrence relation must look something like :
$$T(n) = 2T\Big(\frac{n}{2}\Big)+k$$
What I could understand from the question is that $g(x)$ is applied on all the $n$ nodes and  instead of $k$ it must be something of the order $O(n)$ but I'm not sure what it is. Am I heading in the right direction?


texts:
Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference. A symmetric difference of sets A and B is the set (A \ B) ∪ (B \ A).

I know that the class of decidable languages is closed under symmetric difference, because it is closed under union, complement and intersection. However, does this also apply to the class of partially decidable languages?


texts: How to solve the following recurrence? $T(n) = 4T(\frac{n}{2})+n!$

texts:
Hello all I am kinda confused on how to solve the above recurrence since the masters theorem would not work with the above equation. Could anyone please help me solving this and showing me the steps? Requirement is to find asymptotically tightest bound.

$$T(n) = 4T(\frac{n}{2})+n!$$


texts: Algorithms with O(sqrt(N)) SPACE complexity?

texts: Are there any known algorithms for formulated problems that require a SPACE complexity of O(sqrt(N))? I know that algorithms with that big-O time complexity exist.


texts: How to minimize this DFA using given algorithm?

texts:
I am trying to use Myhill-Nerode theorem to minimize the DFA appearing below.

The algorithm repeatedly runs the following step:

  If there is an unmarked pair $(Q_i, Q_j)$, mark it if the pair $\{δ (Q_i, A), δ (Q_j, A)\}$ is marked for some input letter.

Initially only $\{0,3\},\{1,3\},\{2,3\}$ are marked.
However, $\{0,1\}$ or $\{0,2\}$ won't be marked since the don't have common edges,
$\{1,3\},\{1,2\}$ or $\{2,3\}$ only goes to state 3 with edge 3, but there is no such pair $\{3,3\}$. Then it seems no minimization can be done.

The minimized DFA, however, should merge states 1 and 2.


texts:
I am familiar with free and bound variables theory , but while learning I somewhere saw
this lambda expression

  ((lambda var ((fn1 var) & (fn2 var))) argument)

From what I have learned it seems to me as var is bounded in both fn1 and fn2. But the reference from where the expression is taken says that both var are free and hence  can be substituted by argument while doing β-reduction .

Someone please clear my doubt.


texts:
Let $P$ be a transition matrix of a random walk in an undirected (may not regular) graph $G$. Let $\pi$ be a distribution on $V(G)$. The Shannon entropy of $\pi$ is defined by

$$H(\pi)=-\sum_{v \in V(G)}\pi_v\cdot\log(\pi_v).$$

How do we prove that $H(P\pi)\ge H(\pi)$ ?


texts:
I read that the mapping for user-space processes is changed after each process switch. By mapping I mean the translation from virtual addresses to "real" memory address. I thought that processes are loaded into RAM and are held there (that's what the RAM is for). So the addresses in "real" memory addresses shouldn't change too much over time, because the process is held in RAM.

Where am I mistaken?


texts:
Consider the "Generalized Geography" game: on directed graph G with selected start node, players take turns moving along edges, without ever going back to previously visited nodes.  Last player to move wins.

  GG = {  : G is a directed graph, b is a node in G, and the next
                     player to play has a winning strategy for generalized
                     geography from start node b, i.e., there are moves for
                     the next player to win no matter how opponent plays }

This problem is well-known to be in PSPACE and EXPTIME-hard. My question is:
If we allow repetitions in GG, it still belongs to EXPTIME-hard?


texts: proving $E_{TM}$ is undecidable using the halting language

texts:
How to prove that:

$E_{TM} = \{\langle M\rangle\mid M \ is\ a\ TM\ and\ L(M)=\emptyset\}\notin R$
(is undecidable)

using the language:

$H_{halt}=\{(⟨M⟩,w):M\ halts\ on\ w\}$.

I tried to prove by contradiction that assuming $E_{TM}\in R$ I have a Turing machine which decides $E_{TM}$ and to construct with it a turing machine which decides $H_{halt}$ but I don't know how to do so.


texts: Misconception in taking Pumping Length of language {a} to be $2$

texts:
I would like to know why the pumping length of language {a} is $2$ as said in this chat discussion.

Eventhough this discussion proves  trivially  that the pumping length of language {a} is $2$ I couldn't get by an example how the pumping length of language {a} becomes $2$.Could anyone help me with an example.


texts:
Given a weighted directed acyclic graph (DAG), I need to find all maximum weighted paths between the start node(s), i.e. zero incoming edges, and the end node(s), i.e. zero outgoing edges. My current approach is doing the followings.

Add an extra node $S$ (source) and put directed edges to all starting nodes with zero weight. Similarly, add a sink node $T$ and put directed edges from all end nodes to $T$ with zero weight. Now, the problem is to find all maximum weighted paths between $S$ and $T$. Make the edge weights negative, i.e. weight $w$ becomes $-w$. Find the all single-source shortest path from $S$.

My question is, if there is any other efficient method to achieve this. The other thing is that, I need to find all maximum weighted paths if there exists more than one such paths. How can I find all maximum weighted paths efficiently?

Does maximum flow algorithm help?


texts: Prove that PRE-WORK-POST is Turing Complete

texts:
This is a homework question and I am trying to fully understand what I have to do and how to go about it. Therefore, I don't want full answers to the question.
The programming language PRE-WORK-POST is defined as follows:

Let P, Q, R be LOOP Programs. Then "PRE P WORK Q POST R END" is a PRE-WORK-POST program, whereby PRE-WORK-POST starts of by executing the program P, then executes program Q until $x_0 \neq 0$ and then finally executes program R. Show that the program PRE-WORK-POST is Turing complete, where you have to prove that all WHILE, GOTO, Turing and $\mu$-recursive functions can be simulated by a PRE-WORK-POST program. (All input values of the program are in $x_1,..., x_k$. All other variables are initialised at $0$ and the output value has to be in $x_0$.)

Here's what I have understood. We have the programs P,Q,R and the programming language PRE-WORK-POST. We want to show that all WHILE, GOTO, Turing and $\mu$-recursive functions can be simulated by a PRE-WORK-POST program. Since GOTO $\equiv$ WHILE $\equiv$ Turing Machine $\equiv \mu$- recursive, it is enough to show that any of the four can be simulated using PRE-WORK-POST.  When the program starts, it first executes the program P (which is a LOOP program). It then executes Q until $x_0 \neq 0$ and then finally executes R.
Since P,Q,R are all LOOP programs and all LOOP programs either assign a value to a variable, increment a variable, execute one program after another $P_1; P_2$ or LOOP $x$ DO $P$ END. This means that I have to simulate GOTO, WHILE, Turing Machine or $\mu-$recursive using these four different options.
All that is clear but I'm confused about the actual execution of the program. If we don't assign a value to a variable and start using it, that variable gets assigned the value of $0$. So if we don't assign $x_0$ any value, it is automatically equal to $0$. So how can Q be executed?
I need help understanding how PRE-WORK-POST will work.


texts: NSPACE for checking if two graphs are isomorphic

texts:
I was studying nondeterministic Turing Machines and came across the following question:

Describe a nondeterministic Turing Machine (NTM) that only accepts two graphs (G1 and G2) if they are isomorphic, and provide the NSPACE. The NTM should use as little space as possible.

My attempt at answering this question goes something like this:

If G1 and G2 have different no. of vertices and/or edges, reject
Nondeterministically reorder the vertices v1 thru vn in G1. Leave G2 alone.
Check if there is a bijection from G1 to G2, with the above vertex mapping. If so, accept.

At some point, the above algorithm will go thru all n! possible orderings of G1's vertices, and will exhaustively check to see if there's a bijection.

Not quite sure what the NSPACE() value is, though, or how I would go about computing it. My guess is that re-ordering G1's vertices v1 thru vn will take up n cells of the work tape, and checking every pair of vertices for bijection will require a small additional amount of space that can be reused for each subsequent pair? Or do we actually need to store all C(n, 2) pairs per graph?

This is all very confusing, and I'm unsure whether I'm thinking thru this problem the right way. I'd appreciate any help.


texts: How can i fill shelves with products so that I have the maximum amount of sales?

texts:
I have to do a project where I write a greedy algorithm to maximize a company's sales. There are 6 shelves, each with 8m length. I have to position 100 items whose length, value and max sales possibility I know on those shelves. My problem is, according to my instructions the max sales possibility changes according to the shelf height and the product's position on the shelf. More specifically, it says that the product position at the beginning of the shelf have a max sales possibility that is 30% reduced from those at the end, that the max sales possibility appears at the 4rth shelf and the highest and lowest have 30% of the max.
I would really appreciate any help you can give me as my background is not on computer science and I'm pretty lost. I've tried searching for information on bin packing problems but I haven't found anything that matches.


texts: Clarification reg. jump consistent hashing

texts:
I was reading the paper on Jump consistent hashing, and I'm having some trouble understanding one particular line (page 5, paragraph 2)

"Since we want P(j ≥ i) = (b+1) / i, we set P(j ≥ i) iff r ≤ (b+1) / i."

My understanding is that:

P(j ≥ i) is the probability that a key "jumps"/moves to a different bucket after bucket#i
r is a pseudo random number between [0, 1) with a uniform distribution
b is the last bucket# for which a jump occurred for this key

In particular, I am having trouble understanding this phrase: "we set P(j ≥ i) iff".

Set it to what? Do they mean to say "We want a key to jump to a different bucket ≥ i with a random probability r. This means that P(j ≥ i) ≥ r, which implies that (b+1)/i ≥ r. Hence the smallest such bucket number is obtained by the equation i = floor((b+1)/r)"?


texts:
I'm creating an application where client connects to server, retrieves some data and after that connection is closed.
He spends some time changing that data and then connects again to the server sends it back and connection is closed.
At server data is compared with original and saved to database if it validates.

I see only one solution to this - creating two ServerSocket one for input and one for output. But it does not seem good solution. Is this the way to do it or is there something else? How can I determine purpose of connection?

PS I'm using JAVA 8.


texts: Quicksort Algorithm with Pivot element as Median

texts:
I have read that when pivot element is choosen as Median, then QS Algorithm gets nearly balanced splits and have time complexity of O(nlogn), but my doubt is what if all the elements of the input are same like (2,2,2,2,....,2) and pivot is still the median element, then what type of partitions QS will get as left and right subarray and what will be the time complexity. O(nlogn) or O(n^2)

This is not a homework question, I'm not in school/college anymore.


texts: Does Multitape reduction to a one tape machine preserve space complexity?

texts:
Suppose a Turing machine $M$ has a read-only input-tape and $k$ read-write work-tapes whose non-blank cells are each bounded by $f(|x|)$ where $|x|$ is the length of the input.

Is there some constant $C(k)$ and Turing machine $M^{'}$ with a read-only input tape such that $M^{'}$ accepts exactly when $M$ accepts, $M^{'}$ has only one read-write work tape, and the blank cells of that tape are bounded by $C f(|x|)$?

If there doesn't exist such a constant $C(k)$ that is independent of $M$, does there exist a constant $C(k, M)$?  In other words does reducing the number of tapes preserve space complexity?


texts: Will Java's hashCode() reduce collisions regardless of table size?

texts:
for a class project we have to count the number of collisions from inserting words from a plaintext document into a hashtable. I read that using prime numbers for table sizes can offset the collisions resulting from a poor hashing function.

Do I have to create a poor hashing function to demonstrate the effects of table sizes on collision? Right now I am using Java's native hashCode() method as the key and am passing it into a hashing function to get the index. I passed the generated hashCode into variations of hashing functions, but found no difference in # of collisions between prime/non-prime table sizes.

//Hashing function
    scale = rand.nextInt(prime−1) + 1;
    shift = rand.nextInt(prime);
    private int hashValue(K key) {
                return (int) ((Math.abs(key.hashCode()*scale + shift) % prime) }

I also implemented quadratic probing, but my book says it should result in more collisions if the table size is non-prime.. I would really appreciate your advice.


texts: Why is particular token missing in LALR lookahead set?

texts:
I ran the following grammar (pulled from the dragon book) in the Java Cup Eclipse plugin:

S' ::= S
S ::= L = R | R
L ::= * R | id
R ::= L

The items associated with state 0 given in the Automaton View are as follows:

S ::= ⋅S, EOF
S ::= ⋅L = R, EOF
S ::= ⋅R, EOF
L ::= ⋅* R, {=, EOF}
L ::= ⋅id, {=, EOF}
R ::= ⋅L, EOF

Shouldn't the last item's lookahead set be {=, EOF}? This item could be derived from S ::= ⋅R (in which case the lookahead set is {EOF}) or from L ::= ⋅* R (in which case the lookahead set is {=, EOF}).


texts: A question about the work per recursive call in FPT vertex cover of size k algorithm

texts:
I have been looking at the FPT(Fixed Parameter) algorithm for checking if a vertex cover of size k exists.The algorithm goes as follows:
VertexCoverFPT$(G, k)$
if $G$ has no edges then return true
if $k=0$ then return false
let $uw$ be some edge of $G$
if VertexCoverFPT$(G-u, k-1)$ then return true
if VertexCoverFPT$(G-w, k-1)$ then return true
return false
Its said that this algorithm has $2^k$ recursive calls each with $O(n)$ of work in each recursive call. My question is how is it that there is only $O(n)$ work in each recursive call when we need to create the 2 graphs ${G-u}$ and ${G-v}$ (u and v are the vertices we are currently checking) which takes $O(V+E)$ time (Doing a deep copy of graph G excluding the node and the edges connected to it). Is there a more efficient way than constructing ${G-u}$, ${G-v}$ from G or am I missing something?


texts:
I'm having some trouble interpreting the camera matrix $K = \begin{bmatrix} f_x & s & x_0 \\ 0 & f_y & y_0 \\ 0 & 0 & 1 \end{bmatrix}$ after it multiplies some 3D vector.

Assume that $f_x = f_y = f$ and $s = 1$

$\begin{bmatrix} f & 1 & x_0 \\ 0 & f & y_0 \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} X \\ Y \\ Z \end{bmatrix} = \begin{bmatrix}Xf+Y+x_0Z \\ Yf + y_0Z \\ Z \end{bmatrix} \propto \begin{bmatrix} \frac{X}{Z}f + \frac{Y}{Z} + x_0 \\ \frac{Y}{Z}f + y_0 \\ 1\end{bmatrix}$

So the last vector is the imaged point in homogenous coordinates. However, I'm having trouble interpreting what each of the components are physically doing. An explanation would be much appreciated!

I should mention that I'm familiar with the constants, focal length, skew, and principle point. I just can't tell what they are doing in this configuration.


texts: Which is more fundamental: key-value or subject-predicate-object?

texts:
There seems to be two approaches to store data in NoSQL databases:

Key-Value - The Key is usually stored in a hash-table referencing a Value, or Object, which can be either a key (with specific semantic) or any arbitrary data. Examples are Riak, Redis, Dynamo, CouchDB...

Subject-Predicate-Object - Subject and Predicate are interpreted as keys and Object can be either a key or an arbitrary data. This will cover not only all RDF stores, but also graph databases. Examples are Neo4j, Virtuoso, AllegroGraph...

Now I am not that interested in exact definition and which database falls into which category. We know that there are plenty of RDF triple stores implemented on top of SQL databases, as well as that any SQL database can be represented using only RDF triples. And there are other database types too, like column and document databases.

I am interested in finding out which representation is more fundamental in the sense that for example for a given processor assembler is more fundamental than C (because C is written in assembler) and C is more fundamental than Erlang (because Erlang is written in C), and so on. Or also that binary representation is more fundamental than any other (octet, decimal, hexadecimal) because it uses the smallest amount of different numbers (0 and 1). Unfortunately I don't have a strict definition of what more fundamental means exactly.

In other words, if we assume the following:

A Key is an IRI resource (globally unique identifier, like used in RDF)
A Blob is some arbitrary binary data we can't interpret

Then we can define the following two database types:

Key-Value: Where Key is an IRI and Value is either an IRI or a Blob
Subject-Predicate-Object: Where Subject, Predicate are IRIs, and Object is either an IRI or a Blob

In particular, those would be the fundamental data types stored in those two databases:

Ad 1: Key-Key, Key-Blob

Ad 2: Key-Key-Key, Key-Key-Blob

I have no doubt that any data stored in any database type (graph, column, table, key-value, triple, etc) can be represented in either of those databases. I have also no doubt that data stored in one of those databases can be represented in the other, for example let's assume to represent a Key-Value pair as {Key, Value} and Subject-Predicate-Object as {Subject, Predicate, Object}. Then:

Example 1:

{1, "abc"} can be represented as two triples {2, 3, 1}, {4, 3, "abc"} where 2 means Key, 3 means Stores or Holds, 4 means Value.

Example 2:

{1, 2, "abc"} can be represented as three tuples {1, 1}, {1, 2}, {1, "abc"} where Key = 1 means triple number 1, Value = 1 means Subject position, Value = 2 means Predicate position, Value = 3 means Object position.

The means is a conceptual shortcut for having a proper IRI representing that meaning.

Is there any scientific evidence that one representation is more fundamental than the other? Or, because there is no strict definition of "more fundamental", if we could put it as which representation can more easily and/or efficiently represent data stored in any other database type? And I am asking that because I hope that there isn't just an answer like "it depends" :)


texts: Looking for a paper comparing NLP methods with Data Mining techniques

texts:
I've recently attended a conference, where one of the participants mentioned a recent paper published by a Google employee, which showed that using data mining techniques in application to NLP might sometimes give better results than using the NLP methods themselves.

That was the only description he gave and on top of that, he didn't remember author's name.

Is anyone familiar with such paper?


texts: Which Machine Learning algorithm should I use for gender tagging of words in NLP?

texts:
I have a dataset of about 26,000 words along with their gender tags [m, f or any]. Which ML algorithm should I use for Gender Tagging/Classification purpose. How should I go about it? What should be the input features?

Given a word , it's Part Of Speech tag and in some cases the singularity I am trying to predict the gender of the word.


texts: Optimal strategy for tossing three dependent coins

texts:
Suppose that I have three correlated coins. The marginal probability of Head of coin $i$ is denoted by $p_i$.

The conditional probability of head for coin $i$ given the outcomes of coin $j$ and $k$ is denoted by $p_i|x_j,x_k$, where $x_j,x_k\in\{H,T\}$. We can similarly construct the conditional probability of $i$ given $x_j$.

Each coin can be tossed at most once and you receive a \$1 for a head and -\$1 for a tail. You don't have to toss all the coins, and your objective is to maximize the total reward.

What would be the optimal sequence of tossing coins in this case?

If the coins are independent of each other, the order wouldn't matter. The optimal strategy should be "flip coin i if $p_i>\frac{1}{2}$". For the case of two coins, it can be shown that it is always the best to flip the coin with a higher marginal $p_i$. However, this doesn't have to be optimal for three coin cases. I've been thinking about this problem for a quite long time but can't come up with a general solution or an intuition that might help..


texts: Given a constant k, find the biggest possible rooted tree, if for every path from root to leaf, the sum of the arity of its nodes equals k?

texts:
As an example, here are all possible trees for the case $k=3$:

On each node written is its arity (= the number of children).

While this should be solvable by dynamic programming, I think there was a combinatoric result on this (either exact or a rather fine grained upper bound). Does anybody know it?

Edit:

The size of the tree is the number of nodes it has, so the biggest tree would be the one with the maximum number of nodes.


texts: Max independent set in planar graphs PTAS proof

texts:
I've been searching a few hours for a proof to Max independent set in planar graphs beeing in PTAS but I couldn't find anything, I'm searching for one without any reductions and I wonder if anyone here can help me find one.

Thanks in advance.


texts: Consider vectorization and for loop, do both approaches have the same time complexity?

texts:
I am learning this post

  Fast computation of nearest neighbors is an active area of research in machine learning. The most naive neighbor search implementation involves the brute-force computation of distances between all pairs of points in the dataset: for N samples in D dimensions, this approach scales as $O[D N^2]$.

Consider knn on iris dataset, which has 150 samples of 4 dimensions.

Here are 2 pieces of Python3 code.

code_1: vectorization

(np.sqrt(np.sum(X*X,axis=1)[:, np.newaxis] - 2*np.dot(X,Y.T)
             + np.sum(Y*Y,axis=1)[np.newaxis, :])).reshape((-1,))

code_2: for loop

[np.sqrt((X[0]-Y[0])**2 + (X[1]-Y[1])**2 +
    (X[2]-Y[2])**2 + (X[3]-Y[3])**2) for Y in trainData]

Do both vectorization and for loop have the same time complexity $O[D N^2]$?

The analysis does not have to be based on Python; C or C++ is also appreciated.

This question is code-independent, it is not about how Python implements some operations. it is only about 2 approaches for matrix operations, vectorization and for loop.


texts:
I'm trying to work through various exercises in Skiena's "Algorithm Design Manual." One problem that I am stuck on is as follows:

What value is returned by the following function? Express your answer as a function of n. Give the worst-case running time using Big Oh notation.
function conundrum(n)
    r:=0
    for i:=1 to n do
        for j:=i+1 to n do
            for k:=i+j-1 to n do
                r:=r+1
    return(r)

My first attempt at this problem began with trying to solve it when $n$ is even and my first observation was that $r$ is never incremented for any value of $i$ greater than $n/2$ (I am assuming that a statement along the lines of "$k:=l$ to $n$" is not executed for any $l>n$. Indeed, upon working out the above function for several different values of $n$, I thought that I could intuit that the sum calculated by the function had the following form $\sum_{p=1}^{n/2}\sum_{q=1}^{2p-1}q$-- to intuit this, I began the first loop at $i=n/2$ and worked backwards. Working this sum out, I got $\frac 1 {24} n(n(2n-3)-26)$. To my dismay, upon checking this answer, I found that the correct answer for even $n$ is $\frac 1 {24} n(n+2)(2n-1)$. Any thoughts or hints about what I am doing wrong?


texts: Fitting a regular grammar to strings from a PCFG: how big does it get?

texts:
Let $G=(V, \Sigma, R, S)$ be a (non regular) probabilistic context-free grammar, and $u_1, \ldots, u_n$ a set of $n$ strings generated by $G$.

For finite $n$, it is always possible to find a regular grammar $\hat G=(\hat V, \Sigma, \hat R, S)$ which generates the strings $u_1, \ldots, u_n$.

Intuitively, as $n$ goes to infinity, we expect $\hat G$ to get larger: my guess is that the cardinal of $\hat R$ (and maybe also the cardinal of $\hat V$?) would need to go to infinity.

Are there results which formalize this, e.g. by giving a lower bound on these cardinals as a function of $n$?


texts: After how many iterations will an integer circle back to 0 in Python?

texts:
If this question is completely garbage I apologize because I am new to CS and haven't understood at how programming languages (Python specifically) work.

I was reading about how in a standard two-byte representation of a number, if one was to increment 65,536 times, the integer would wrap back to one. Would this case occur in Python, and if so at what number would this occur?

Edit: I read a little bit further into this and it seems that after an increment, programming languages seem to redefine the value. Would this prevent this from occur


texts:
In a layered approach to OS design, each layer can only access routines from the layers below itself.

For example, say I had two levels: memory management and the CPU scheduler

Where does the CPU scheduler sit in a layered OS design?

My understanding is that it must be above the memory management component, since the scheduler needs access to the routines in the memory management layer to be able to select new processes from memory to place on the CPUs ready queue.


texts: What algorithm do computers use to compute the square root of a number?

texts:
What algorithm do computers use to compute the square root of a number ?
EDIT
It seems there is a similar question here:
Finding square root without division and initial guess
But I like the answers provided here more.
Plus the person asking the similar question had the question formed in a personal way.
My question has an easier to find wording.
The similar one was asked having an insight about the inner mechanics of such an algorithm and was being asked like if it was something that had not yet been solved-found.
I don't know if there is a way for a moderator to merge the two posts.


texts: Prove that grammar $S \to aSc | \epsilon | bBc$ ,$B \to bBc | \epsilon$ generates language $\{a^ib^jc^{i+j} | i,j \ge 0 \}$

texts:
Prove that grammar $G$ with productions:

$S \to aSc|\epsilon | bBc$
$B\to bBc | \epsilon$

Generates language $ L = \{a^ib^jc^{(i+j)}$ | $i,j \ge 0 \} $
Step 1. Prove $L(G) \subseteq L$
.
We are inducting on the number of steps in derivation $S \xrightarrow i w$ where $i\ge 1$.

Base case: For $i=1$ is trivial and word generated is $\epsilon \in L$

Inductive Hypothesis: Suppose there's some $n$ such that for all derivations $S \xrightarrow n w$ , $n\ge 1$, a word $w$ is in $L$. So w derived is $a^ib^jc^{n-1}$, where $n=i+j+1$ and $i,j \ge 0$

Inductive Step: Suppose we need $n+1$ steps to derive a word $w$. We can write $S \to aSc \xrightarrow n w$ or $S \to bBc \xrightarrow n w$.

Case 1 $S \to aSc \xrightarrow n w$: Let $w = axc$ such that $S\xrightarrow n x$. By Inductive Hypothesis $x=a^ib^jc^{(n-1)}$. So $w=aa^ib^jc^{n-1}c = a^{i+1}b^jc^{i+j+1-1+1} = a^{i+1}b^jc^{i+j+1}$ And indeed $w \in L$ since $i+j+j=i+j+1$
Case 2: ...
Is case 1 approached in the right way ? In my previous proofs I was able to write a word w in a way that it only had one variable n connected to the number of derivations, but here I also have i and j and not only n.


texts: Mathmatical way to represent an image kernel?

texts:
How to represent the calculation in this image mathematically?

For example: With the discrete convolution
$(f * g)[n]\ \stackrel{\mathrm{}}{=}\ \sum_{m=-\infty}^\infty f[m]\, g[n - m]$
and Fourier transform.


texts: How to prove a segment of a program (Hoare-logic)

texts:
Problem:
A segment of a program is shown below:
⋮
_ _ _ _ _ _
z = x - 7;
(|z = 5 ∧ n = 4|)
⋮

What is the dashed line hiding?
My solution:
I think the dashed line is hiding: (|x - 7 = 5|)
However, I am not sure if it is the correct solution, it would be nice to know how to solve this trivial problem.


texts: Solve X(n) = 2X(n-1) + 2 recurrence relation

texts:
I'm trying to solve the excersice from Knuth's "Concrete
Mathematics":

A Double Tower of Hanoi contains 2n disks of n different sizes, two of
each size. As usual, we're required to move only one disk at a time,
without putting a larger one over a smaller one.

How many moves does it take to transfer a double tower from one peg to
another, if disks of equal size are indistinguishable from each other?

My solution was like this. Let $n$ be the number of disks of
different sizes and $X_n$ - number of moves. The first few solutions
are:

$n = 0$ $X_n = 0$

$n = 1$ $X_n = 2$

$n = 2$ $X_n = 6$

$n = 3$ $X_n = 14$

Recurrence is $X_n = 2X_{n-1} + 2$

We can add $2$ to both sides:

$X_n+2 = 2X_{n-1} + 4$

let $Y_n = X_n + 2$, then

$Y_n = 2Y_{n-1}$

$Y_n = 2^n$

$X_n = 2^n - 2$

The problem is that the correct solution is $2^{n+1} - 2$, but I
cannot find an error in my approach.


texts: Proof Check: The class L is closed under concatenation

texts:
I want to prove that the class of all Turing machines that use a logarithmic amount of space is closed under concatenation. The basic idea of my proof is this: given a word, to check if it's in $L_1L_2$, simply look at all possible $n+1$ ways to slice the word into 2 parts and check if the first part belongs to $L_1$ and if the second belongs to $L_2$.

Because both of the languages can be decided in logarithmic space, checking one after the other can also be done in logarithmic space.

Is my idea correct? Thanks.


texts: Represent polynomial time complexity as linearythmic

texts:
To determine the experimental time complexity of radix sort, I wrote a program that counted the number of steps the algorithm took to sort N points. I ran that program for multiple N length arrays, and I plotted the steps taken in Excel. Then, using the trend line tool, I calculated the polynomial that best fit the function.

It gave me something along the line :
$$Steps = 16n^{1.0932}$$

This seems to be $O(n)$, but my prof is telling us to represent this as $O(n \log n)$ . How would I go about to demonstrate this.

Thanks.

PS: If anyone is interested, here are my results.


texts:
If this link can be any help

https://codeforces.com/blog/entry/63164

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.

A minimum vertex cover is a vertex cover with minimal cardinality.

Consider a set of all minimum vertex covers of a given bipartite graph.

our task is to divide all the vertices of the graph into three sets.

A vertex is in set N (“Never”) if there is no minimum vertex cover containing this vertex.

A vertex is in set A (“Always”) if it is a part of every minimum vertex cover of the given graph.

If a vertex belongs neither to N nor to A, it goes to the set E (“Exists”).

How to classify vertices?

I don't understand the variables. I have an edge from maximum matching then I might have both the endpoints of that edge in the vertex cover. But this scheme does not allow this.

http://acm.timus.ru/problem.aspx?space=1&num=2038


texts: Storing binary tree with arbitrarily sized nodes without linked-list or large 32-bit pointers

texts:
So you can store a binary tree without pointers using a 1-D array:

  Binary Trees can be represented using 1-D array in memory(Fig 1).The rule to store binary tree in array are :

  The values of binary tree is stored in an array called as tree.
  The root of the tree is stored at first location i.e. at  tree[0](0 index).
  The left child of tree is stored at  2i +1 and right child is stored at  2i+2 location.
  The maximum size of the array tree is given as  2d+1-1, where d is the depth of the tree.
  An empty tree or sub-tree is specified using NULL. If tree[0] = NULL, then it means that tree is empty.

But this assumes the items are all the same size. In my case I'm wondering how to store them when the nodes contain arbitrarily sized data. You can do this by storing them using linked lists, but the problem with linked lists is they require pointers, and pointers are usually 32-bits which means they're large enough to point to anywhere in the typically available memory on most standard computers.

This is kind of a hack. You're basically doing absolute addressing for the nodes, where each pointer is an absolute address to the node. I'm instead wondering if there is any way to use relative addressing. That is, you say where the linked node is relative to the current node. This would allow for a linked-list like situation -- so it solves the dynamically sized records problem -- but without absolute addresses. I am having difficulty though, without having the advantage of absolute pointers, of how relative pointers might work with a tree.


texts:
I'm trying to prove that every language that is not the empty set or {0,1}* is complete for NL (nondeterministic logarithmic space) under polynomial-time Karp reductions.

I'm really not sure how to even approach this problem or what languages are being discussed if you exclude both the empty set and {0,1}*. Any suggestions to get me going in the right direction? Thanks!

Edit:

I feel like I may still be understanding the problem incorrectly. I seem to be finding that polynomial-time reductions can't be used to define NL completeness, but that's what I feel this question is asking. What am I thinking about wrongly here? Thanks.


texts: Proving that $L = \{ a^{n!} \ | \ n \geq 0 \}$ is not regular

texts:
Let $L$ a language over $X = \{a\}$ defined as follow :

$$L = \{ a^{n!} \ | \ n \geq 0 \}$$

I want to prove that $L$ isn't regular, I have searched in the forum for an equivalent question, but I found nothing. If it's a duplicate, I apologize and I'll be glad if you provide me the link of the duplicated question.

I'll show here what I have done, using the pumping lemma.

Suppose that $L$ is regular, let $n \in \mathbb{N}^*$ and $\omega = a^{n!}$. We have $\omega \in L$ and $|\omega| \geq n$. Thus, there exist $x, y, z \in X$ so as :

$a^{n!} = xyz$
$y \neq \epsilon$
$|xy| \leq n$
$xy^kz \in L, \quad \forall k \geq 0$

Because of fact 3, $xy = a^k$ and $y = a^j$ with $k \leq n$ and $1 \leq j \leq n$. Thus :

$$a^{n!} = a^{k - j}.a^{j}.a^{n! - k}$$

By fact 4, we must have $a^{k - j}.a^{n! - k} = a^{n! - j} \in L$.

In addition, because $1 \leq j \leq n$, the following is true :

$$n! - n \leq n! - j \lneq n!$$

The final result that I need is that $(n - 1)! \lneq n! - n$. Using this I can deduce :

$$(n - 1)! \lneq n! - j \lneq n!$$

Showing that $n! - j$ can't be the factorial of an integer, giving the contradiction $a^{n! - j} \notin L$. I have tried to prove the final result, but I didn't succeed. It is not true for the first values of $n$, I have tried to consider multiple cases but went for nothing.

So I ask for your advice, maybe I am going wrong and didn't applied the pumping lemma with a word that leads to contradiction.


texts:
this is the recursion formula for problem :
C(i,S) = min { d(i,j) + C(j,S-{j}) }

In fact, when I tried to implement it as a code, the following code came to my mind:
int TSP(i, S){
    if(S.size == 0)
    return dist(start_vertex,i)
min = inf
cost = inf
  for(int j=0;j<S.size;j++)
     {
      cost = dist(i,S[j])+TSP(j,S-{j});
      if(cost < min)
       min = cost;
      }
global_cost+=min;
return min;
}

Because this for compares n times to find the minimum, it means its recursion as:
T(n) = nT(n-1)+n ==> T(n) = O(n!)

Because each step we compare to find the minimum size of size S is, of course, the code is factorial. So what does it have to do with the subset and So why the complexity of time in the form of (n^2*2^n)? And what is the proof of its time complexity?


texts: How to find the spot which is furthest away?

texts:
Last night I thought about the following problem:

Given any map (for example from Germany), how to find the spot which is furthest away (in every direction) from the nearest (any) town/village?

I thought about how one would proceed to figure out in which problem class this problem belongs to and how to prove that.
And also how to determine which would be an efficient algorithm for this problem.
Basically I would like to learn about the steps how a professional in complexity theory would start to work on a problem like this.

I read on Wikipedia about the Nearest neighbor search which I think come close to what I'm looking for. But I wasn't able to find something like "furthest neighbor search".


texts: About having analytic control over any algorithm which finds perfect matchings.

texts:
A trivial algorithm to decompose a degree-d (n,n)-bipartite graph into d disjoint perfect matchings is this :  direct all the edges from left to right and put capacity one on each of them - then add a super-source and a super sink with appropriately directed edges from them to each of the vertices on their side with capacity one - now run max-flow on it and that picks out a perfect matching - now remove this perfect matching and repeat - continue doing this till you have exhausted all the original edges - this clearly gives you the needed decomposition of the original graph into disjoint perfect matchings.

So one can think of this algorithm as basically returning you a set of d disjoint permutations on the set of n elements.

Can one say what permutations will be returned? (Will it always return the same set of permutations in the same sequence?)
Its possible that the answer to the above question is implementation dependent and in that case is there some "standard" implementation for which one can analytically write down the permutations that would be returned as a function of the input graph?
Or is there any other way to solve this question where one analytically knows the permutations that will be generated?


texts: Is it possible to reduce the number of variables in bin packing?

texts:
The bin packing problem can be formulated as:
\begin{align}
 & \underset{x,y}{\min}
 & & B = \sum_{i=1}^n y_i\\
 & \text{subject to}
 & & B \geq 1,\\
 & & & \sum_{j=1}^n a_j x_{ij} \leq V y_i,\forall i \in \{1,\ldots,n\}\\
    & & & \sum_{i=1}^n x_{ij} = 1,\forall j \in \{1,\ldots,n\}\\
    & & & y_i \in \{0,1\},\forall i \in \{1,\ldots,n\},\\
    & & & x_{ij} \in \{0,1\}, \forall i \in \{1,\ldots,n\}, \, \forall j \in \{1,\ldots,n\},\\
\end{align}

where $y_i = 1$ if bin $i$ is used and $x_{ij} = 1$ if item $j$ is put into bin $i$.

Why do we use $x_{ij}$ and $y_{i}$? We can just use $x_{ij}$.

if $x_{ij}=1$ than bin $i$ is used and item $j$ is put into bin $i$; and
if $x_{ij}=0$ than bin $i$ is not used.

Is that correct? If so, why can't I find any formulation with only $x_{ij}$?


texts: Find minimum pair number based on selection algorithm

texts:
If we have n balls in a red box (each ball is assigned a different number from 1 to n) and n balls in a green box (again each ball is assigned a different number from 1 to n). Lets say we have a player that chooses randomly a ball from each box and throws it on the floor. If we can predict exactly the time when a pair (red ball and green ball) given their numbers will be chosen (ex. input: red ball 5, green ball 6 output: 5sec ) , can we find the pair that will be chosen first in O(n) time?

The predictions costs: O(1) for each pair we input. We can predict as many pairs as we want

I have thought the simple solution: Predict every pair and then choose the minimum time, but that would cost $O(n^{2})$. I cannot optimize this further


texts: Count unique increasing subsequences of length 3 in $O(n\log n)$

texts:
Problem: Given an array of $n$ integers, $A[1 \dots n]$, such that any integer occurs at most 2 times in the array, we have to find the number of unique increasing subsequences of length 3 (duplicate subsequences must be counted only once). In other words, we have to count the number of unique integers $A[i], A[j], A[k]$ such that $A[i] < A[j] < A[k]$ with $i < j < k$.

I have been stuck on this for quite a while now. I did look up this question which tests for the existence of such a triplet. But I think my question is different because it needs the count, and because it needs unique triplets (upto 1 repetition of any number is allowed).

Idea: $O(n^2)$ algorithm. For each number, we can scan the remaining array and find out how many unique numbers are greater than it and occur after it. This can be done in $O(n^2)$ by naive brute force. For every pair of numbers ($O(n^2)$), we now have the number of possible triplets that can be formed by using the pair as the first two numbers of the triplet (since we know how many are greater than the second number).

Unfortunately, $O(n^2)$ is too slow, and I need a faster solution - $O(n\log n)$ or $O(n)$. Space complexity also has to be sub-quadratic. I was thinking along the lines of sorting a copy of the array to find out the relative rank of each element, but could not go any further. Any help or hints are greatly appreciated!


texts:
In section 6.3 of the paper Causal memory: definitions, implementations, and programming, the authors define "data-race free" as follows:

Program $\Pi$ is data-race free if, for all histories $H$ of $\Pi$ and all causality orders $\leadsto$ of $H$, if $H$ has a serialization that respects $\leadsto$ (note that this implies that $H$ is sequentially consistent), then $H$ is data-race free with respect to $\leadsto$.

The one-sentence definition is too complicated for me to follow. It involves various notions and their relations. Specifically, a program is a set of its histories. Given a history, there may be more than one causality order for it, because there may be multiple writes of a value to a variable and thus more than one writes-into order. Let $H$ be a history with causality order $\leadsto$. We have to consider whether it is sequentially consistent and data-race free with respect to $\leadsto$.
The following image enumerates all the possible classes of executions which I can think of produced by any program. The red crosses in the image indicate non-existence. For instance, the "path" $\Pi - H_1 - \leadsto_{12} - S_{12} - DRF_{12}$ means that $S_{12}$ is a serialization (thus sequentially consistent) of history $H_1$ that respects $\leadsto_{12}$ but is not data-race free with respect to $\leadsto_{12}$.

EDIT: Here are some explanations of this image. For any program, there are five possible classes of executions. $H_0$ indicates the class of executions which have no causality orders at all (i.e., it causality orders are cyclic). The executions like $H_1$ have more than one causality orders, such as $\leadsto_{11}, \leadsto_{12},$ and $\leadsto_{13}$. However, $H_1$ (as a representative of its class) is not sequentially consistent respecting $\leadsto_{11}$ (denoted by the red cross over $S_{11}$); $H_1$ is sequentially consistent respecting $\leadsto_{12}$ but is not data-race free with respect to $\leadsto_{12}$ (denoted by the red cross over $DRF_{12}$); and $H_1$ is sequentially consistent respecting $\leadsto_{13}$ and is data-race free with respect to $\leadsto_{13}$. The cases for $H_2$, $H_3$, and $H_4$ are similar.
Here comes my first problem:

(1). What are the classes of executions excluded by "data-race free"? (and does the image miss some classes of executions?)
In my opinion, only the executions like $H_1$ are excluded. The reason is that the "path" $\Pi - H_1 - \leadsto_{12} - S_{12} - DRF_{12}$ violates the definition of "data-race free".

Immediately following the definition of data-race free, the authors show that data-race free programs produce only sequential consistent executions when run on causal memory:

Theorem 5. If $\Pi$ is data-race free, then all histories of $\Pi$ with causal memory are sequentially consistent.

In the first paragraph of its proof, it says that "Let $H$ be a finite (infinite) causal history and let $\leadsto$ be a causality order that proves that $H$ is causal. We will prove that $H$ is data-race free with respect to $\leadsto$ and has a serialization that respects $\leadsto$".
Here come my other two problems:

(2). Back to the image above, does the theorem mean that when run on causal memory data-race free programs produce only the executions like $H_3$ which are both sequentially consistent and data-race free with respect to each of its causality orders?
(3). If so, is it right to conclude that the executions produced by data-race free programs when run on causal memory actually satisfy some stronger consistency model (though not formally defined) than sequentially consistent model?

Besides the answers to my problems, any personal (or even subjective) comments worthy of note on the definition "data-race free" are appreciated.


texts: Why is the word "calculus" used to describe systems of logic and computation?

texts:
Why is the word "calculus" used in this context?

The reason I ask is because these usages of "calculus" seem unrelated to the far more popular use of "calculus" in "differential calculus" and "integral calculus" to which something like λ-calculus seems only very distantly related. This word choice seems very misleading yet very popular among many authors. Why?


texts: Question about the CLRS Linear Programming chapter

texts:
I'm currently reading the CLRS Linear Programming chapter and there is something i don't understand.
The goal is to prove that given a basic set of variables, the associated slack form is unique
They first prove a lemma :

And then they prove the result :

My concern is that to prove the second lemma, they apply the first lemma. However equations (29.79) -> (29.82) only holds for feasable solutions, which is not for any x, so why can they apply the first lemma ?


texts: How to recursively infer a word/string from a context-free grammar?

texts:
Give the recursive inference of the word $abcddd$ from the Context-free Grammar:

  $A\rightarrow aAd\mid B$
  $B\rightarrow bBd\mid C$
  $C\rightarrow cC\mid cD$
  $D\rightarrow Dd\mid ϵ$

This is a follow up question to this one here. Much like that question I haven't found any good information on the subject. I understand the inductive proof of an inferred word belonging to a language, but I don't know how to put it to practical use. I have found an example in our course literature, "Introduction to Automata Theory, Languages, and Computation" by Hopcroft, Motwani and Ullman, but they only have a filled out table of the inference of several words without any detailed explanation on how they got there.

I tried to mimic that table for this excersice and think I have solved it, but I don't understand what I'm doing or if I'm even doing it right. What I need is someone to explain the thinking behind this algorithm or whatever it is they are using. Here is the table I have created for the word $abcddd$:

$$
   \begin{array}{ r | c | c | c | c }
   & \textit{String Inferred} & \textit{For language of} & \textit{Production used} & \textit{String(s) used} \\ \hline
   (i) & ϵ & D & D \rightarrow ϵ & - \\
   (ii) & d & D & D \rightarrow Dd & (i) \\
   (iii) & cd & C & C \rightarrow cD & (ii) \\
   (iv) & cd & B & B \rightarrow C & (iii) \\
   (v) & bcdd & B & B \rightarrow bBd & (iv) \\
   (vi) & bcdd & A & A \rightarrow B & (v) \\
   (vii) & abcddd & A & A \rightarrow aAd & (vi) \\
    \hline
  \end{array}
$$

To me this is just like deriving words, but backwards, if you know what I mean? So, I am doing this correctly? Why am I doing this, instead of just deriving words "as usual"?


texts: An algorithm to turn descending order into ascending order, but why correct?

texts:
Why is this sort algorithm correct? Many thanks!

Task:

Suppose all elements in an array with length $n = 2^m$ are in descending order: $a_1 > a_2 > ... > a_n$, we need to turn them into ascending order.

Algorithm:

For each step from $1$ to $m$:

Swap each adjacent (odd index, even index) pair into ascending order, so that:
$a_1 \le a_2, a_3 \le a_4, ... , a_{n-1} \le a_n$
Move all elements with odd index to the front of those
with even index, so $a_1, a_2, a_3, a_4, ..., a_{n - 1}, a_n$ turns to : $a_1, a_3, ..., a_{n - 1}, a_2, a_4, ..., a_n$

Example:

Sort result after each step with $n = 8$:

[0] 8 7 6 5 4 3 2 1
[1] 7 5 3 1 8 6 4 2
[2] 5 1 6 2 7 3 8 4
[3] 1 2 3 4 5 6 7 8

Code:

#include <stdlib.h>

void swap(int *arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void magic_sort(int *arr, int *result, int n)
{
    int half = n >> 1;
    int i;

    /* Swap adjacent (odd index, even index) pair into ascending order */
    for (i = 1; i <= n; i += 2)
    {
        if (arr[i] > arr[i + 1])swap(arr, i, i + 1);
    }

    /* Move all elements with odd index to front half */
    for (i = 1; i <= n; i += 2)
    {
        result[(i + 1) / 2] = arr[i];
    }

    /* Move all elements with even index to tail half */
    for (i = 2; i <= n; i += 2)
    {
        result[half + i / 2] = arr[i];
    }

    for (i = 1; i <= n; i++)
    {
        arr[i] = result[i];
    }
}

int main()
{
    int m = 3;
    int n = 1 << m;
    int *arr = (int *)malloc(sizeof(*arr) * (n + 1));
    int *result = (int *)malloc(sizeof(*arr) * (n + 1));
    int step, i;

    printf("[%d] ", 0);

    for (i = 1; i <= n; i++)
    {
        arr[i] = n + 1 - i;

        printf("%d ", arr[i]);
    }

    printf("\n");

    for (step = 0; step < m; step++)
    {
        magic_sort(arr, result, n);

        printf("[%d] ", step + 1);

        for (i = 1; i <= n; i++)
        {
            printf("%d ", arr[i]);
        }

        printf("\n");
    }

    free(arr);
    free(result);

    return 0;
}


texts: Simple explanation as to why certain computable functions cannot be represented by a typed term?

texts:
Reading the paper An Introduction to the Lambda Calculus, I came across a paragraph I didn't really understand, on page 34 (my italics):

  Within each of the two paradigms there are several versions of typed
  lambda calculus. In many important systems, especially those a la
  Church, it is the case that terms that do have a type always possess a
  normal form. By the unsolvability of the halting problem this
  implies that not all computable functions can be represented by a
  typed term, see Barendregt (1990), Theorem 4.2.15. This is not so bad
  as it sounds, because in order to find such computable functions that
  cannot be represented, one has to stand on one's head. For example in
  2, the second order typed lambda calculus, only those partial
  recursive functions cannot be represented that happen to be total,
  but not provably so in mathematical analysis (second order
  arithmetic).

I am familiar with most of these concepts, but not the concept of a partial recursive function, nor the concept of a provably total function. However, this is not what I am interested in learning.

I am looking for a simple explanation as to why certain computable functions cannot be represented by a typed term, as well as to why such functions can only be found 'by standing on one's head.'


texts: maximal independent set on grid graph proof

texts:
I'm trying to figure out proof of maximum independent set from: this link. (1b part).
And I'm bit confused why exactly sum of $w(v)$ is less than or equal to sum of $w(v')$.
Shouldn't it be other way around? As we define $v'$ if it is in $T$ and is in $S$


texts:
I have a question regarding the solution provided by Karolis Juodelė.
Given in this question; Colour a binary tree to be a red-black tree

Black = black nodes, white = red nodes

So for this tree when I try to manually work out the code, it seems to fail on the node 17. E.G. I have a black quota of 3 so I color the root black. Afterwards I go to the left child (17) and that has the same min height (namely 17 - 21 - 23) -> so I color this black. After this black colour I cannot see how I will end up with a valid tree with 1 black node left.

So if you could provide how to solve it for this example that would be great!


texts: Checking whether at least n/2 + 1 elements of a set/vector are equal

texts:
We have a set of elements, say a vector of $n$ elements (actually, the data structure really doesn't matter in this case). It is NOT sorted. We want to check whether at least $n/2 + 1$ elements are equal.

I have been thinking about an efficient algorithm to do so but I don't know, the fact that it is not sorted makes it quite difficult for me.

If it was sorted, we could do it with an $O(n)$ algorithm, I'd say: just iterate over the vector, saving the most common element. If the counter arrives to $n/2 + 1$, we are done.

Could you give me some advice? Thank you very much.


texts: Is the Syntax of C Language completely defined by CFGs?

texts:
I think the Question is self sufficient. Is the syntax of C Language completely defined through Context Free Grammars or do we have Language Constructs which may require non-Context Free definitions in the course of parsing?

An example of non CFL construct i thought was the declaration of variables before their use. But in Compilers(Aho Ullman Sethi), it is stated that the C Language does not distinguish between identifiers on the basis of their names. All the identifiers are tokenized as 'id' by the Lexical Analyzer. If C is not completely defined by CFGs, please can anyone give an example of Non CFL construct in C?


texts:
I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$.

I want to find the largest integer value such that it is less than $T$ and not satisfied by $Ax+By+Cz$, how can I do it without using brute force.

I can use LinearProgramming but that will give me the value that is satisfied by $Ax+By+Cz$ such that it is less than T. But I want to find the largest value which is less than T, but doesn't belong to $Ax+By+Cz$ for any value of x, y and z


texts: When average , worst and best case time complexity happens in quick sort?

texts:
I know recurrence relation corresponding to quick sort worst case is

$T(n)=T(n-1)+T(0)+\Theta(n)$

and time complexity is $O(n^2)$.

This happens when we select pivot which is either largest element or smallest element in the current sub problem.

This can occur when array is sorted in either descending or ascending order and we select either largest or smallest element as pivot.

I also know that best case occurs when median is chosen as pivot, giving recurrence relation

$T(n)=T(n/2)+T(n/2)+\Theta(n)$.

and time complexity $O(n \log n)$.

  Statement 1: Any other partition should result in average case.

I have come across problems each time choosing pivot which partition array in some fixed proportion (say $T(n)=T(n/10)+T(9n/10)+\Theta(n)$) ending in average case performance of $O(n \log n)$ (and I understand its proof).

However I have also came across text saying:

  Statement 2: Any pivot which does not partition array in some proportion should result in worst case. If $n$th smallest or largest element is selected as pivot, it will result in worst case.

Q1. Is statement 1 true? If no, which other pivot selection strategies could result in worst case or best case behavior?

Q2. Is statement 2 true?


texts:
I am have a difficult time understanding when a direct map cache is a hit or a miss. My understanding is that when and index matches, but a tag doesn't it is still a miss but the new tag then takes over the previous tag on that index.

Address  Binary Address   Tag       Index   H/M

3        00000011        0000        011    Miss
180      10110100        1011        100    Miss
43       00101011        0010        011    Miss
2        00000010        0000        010    Miss
191      10111111        1011        111    Miss
88       01011000        0101        000    Miss
190      10111110        1011        110    Miss
14       00001110        0000        110    Miss
181      10110101        1011        101    Miss
44       00101100        0010        100    Miss
186      10111010        1011        010    Miss
253      11111101        1111        101    Miss

As such my theory is that all of the mappings are misses, am I correct?

Thank you so much guys!

The block size is one word; therefore we use no offset bit
The total size is 8 blocks; therefore we need only 3 index bits


texts: Search techniques to find desired output with complex interdependencies

texts:
I am trying to generate output consisting of three-tuples (A,B,C), where A,B, and C are three different datatypes representing different values.  I also have a collection of functions $f_i \in F$ which each take in either one, two, or all of A,B, and C as input, and output whether a condition regarding the relevant variables holds or not.  Many $f_i$ compute things about the relationships between A, B, and C.  I want to search for the values of (A, B, C) which maximize the number of elements of F which return true.

What search techniques can I use?  It seems that standard techniques wouldn't preserve good interdependencies between A and B values which already exist in the population.


texts: Assuming $P\neq NP$, is there a computational model in which OWFs cannot exist? What more should we include beyond non-determinism, randomness, quantum model to preclude existence of OWFs?


texts:
I have been given a tree with n nodes and n-1 edges with it's weight.
There are two people A and B.
I have been given a list of nodes of size k.

A will pick a random node x from this list and B will independently pick a random node y from this list.

I have to find expected distance between these two nodes.

My way of solving it was to find the distance between all the (k*(k-1)/2)nodes of the list and dividing it by number of nodes in the list.

for ex:
n=6,k=6 list=[1,2,3,4,5,6]

                    Node--------> 1
                                   \(1)<-----------Weight
                                    \
                                     3
                                (3) / \(2)
                                   /   \
                                  4     2
                             (4) / \ (5)
                                /   \
                               5     6

My answer was coming out to be 87/6 but the actual answer was 29/6.Please help me find whatever i am doing wrong here.


texts: Shortest path from that passes through a set of edges once

texts:
Given a graph with weighted edges. How to find the shortest path from vertex $A$ to vertex $B$ that passes through a set of edges $X$ at most once? $X$ can be big.

Slow solution:
Finding shortest path from $A$ to each edge of $X$ and shortest path from each edge to $B$ in graph $G\setminus{X}$. Combining those paths and choosing the shortest one.

Can anyone think of a faster solution that doesn't require running Dijkstra's algorithm for each edge from $X$?


texts: implementing ExtractMin on a Max-heap in O(log(n)) time

texts: Is it possible to implement extractMin on a Max-Heap in O(log(n)) time, and if so how? Or do you need a more elaborate structure like a max-min heap?


texts:
I have a little problem I have been trying to solve for a hobby after a friend got me interested in fantasy football: given a list of players, positions for those players, projected points, salary, and a salary cap, build the highest projected scoring NFL team that fits the salary cap. I am interested in finding an efficient way to do this.

An NFL team consists of 1 QB, 1 TE, 1 K, 1 D, 3 WRs and 2 RBs. Each position has a varying number of potential players available, but for the sake of argument we can say that from an initial list of about 600 players total, we can safely eliminate most of them so that there are 5-15 players to choose from for each position.

I have "solved" this problem with a brute force approach: I have a separate loop for each position, loop over all available players, and find the best team that fits the salary cap. This works, but having written a function containing 9 nested loops makes me feel dirty. To deal with a dataset with around 10 players in each position as options, it takes about 2 hours to finish. Past that, it would be too slow to be useful.

Several websites out there do exactly this: For Example. However, if you reject a player from their lineup and recalculate, it takes less than a second to find a new optimized lineup. It was pointed out to me that it is possible that they are doing a pre-computation and storing all possible teams in a database, and simply searching through it in order to find new optimized lineups when someone tweaks things, but I am hoping that is not the case.

So the question, finally: is there an efficient algorithm that guarantees an optimal solution, assuming that the best team mean maximizing the sum of projected points for the players on the team?


texts: VC dimension of the class of polynomial classifiers of degree $n$

texts:
I came across this statement on page 85 of the book "understanding machine learning: from theory to algorithms"

The general idea is as follows:

Consider a binary classiﬁcation problem with the instance domain being $X = \mathbb R$.

For every $n \in \mathbb N$ let $H_n$ be the class of polynomial classiﬁers of degree $n$; namely, $H_n$ is the set of all classiﬁers of the form $h(x) = \operatorname{sign}(p(x))$, where $p\colon  \mathbb R \to \mathbb R$ is a polynomial of degree $n$.

Prove that the VC dimension of $H_n$ is $n+1$.


texts: Square or circle neural network detection

texts:
I am trying to use a simple perceptron to recognize if there is a square or a circle on an image. The images I generated are 300x300 px and I am having issues training the network since the images are large and I seem to run out of memory after a few images.

What would be the correct approach for this?


texts: Proving that the two definitions of Universal Class of Hash Function are equivalent (as dealt with in CLRS)

texts:
I was going throught the text Introduction to Algorithm by Cormen et. al. where I came across the two alternative definitions of Universal Class of Hash Function.
The versions are as follows:

Definition 1: Let $\mathscr{H}$ be a finite collection of hash functions that map a given universe $U$ of keys into the range ${0,1,...,m-1}$. Such a collection is said to be universal if for each pair of distinct keys $k,l\in U$, the number of hash functions $h\in\mathscr{H}$ for which $h(k)= h(l)$ is at most $|\mathscr{H}|/m$.

Now in the above definition the authors are using "for each pair of distinct keys $k,l\in U$" to mean that probably we do not leave out any possible key pair for which collision occurs.

Definition 2: With a hash function randomly chosen from $\mathscr{H}$, the chance of a collision between distinct keys $k$ and $l$ is no more than the chance $1/m$ which is the chance of a collision if $h(k)$ and $h(l)$ were randomly and independently chosen from the set $\{0,1,...,m-1\}$.

Through-out the rest of the book the author uses the second definition.
I felt like finding the equivalence of the two definitions.

Definition 1 $\implies$ Definition 2

Definition $1$ says that for a pair of distinct keys says $k,l$ for the set $A=\{h \in \mathscr{H} : h(k)=h(l)\}$ ,
$$|A|\leqslant|\mathscr{H}|/m \tag 1$$
Now if we chose a hash function $h\in \mathscr{H}$ at random then for the said pair of distinct keys $k,l$ we have,
$$ Pr\{h(k)=h(l)\} = \frac{\text{no. of functions in A}}{\text{no. of functions in $\mathscr{H}$}}=\frac{|A|}{|\mathscr{H}|} \leqslant\frac{1}{m} \quad\text{using (1)}$$

I could not quite find a way to show that:
$$\text{Definition 2 $\implies$ Definition 1}$$
Or the way I proved the first implication actually proves the equivalent...
Previously I made an attempt but it was wrong as it was pointed out and so that wrong portion has been edited out.
I had found two similar questions 1 and 2 but it did not quite seem to answer my query.


texts:
Let a matrix $A=0$. Can I say $A$ is nilpotent? I am asking if the zero matrix is nilpotent or not.
Nilpotent means that $A^k = 0$ for some $k$ that is a non-negative integer. When $k = 1$, $A^k = A = 0$. Does this idea support that a zero matrix is nilpotent?


texts:
Suppose I have a array of real numbers with $n$ rows and $m$ columns.  I want to consider possible ways of dividing that array into rectangular regions of three different possible types: a constant value over the entire region, a linear gradient across rows or a linear gradient across columns.

For example, the array

$\begin{bmatrix}1 & 2 & 3 & 10 \\ 1 & 2 & 3 & 12 \\ 4 & 4 & 4 & 14\end{bmatrix}$

can be decomposed into a horizontal gradient [1-3], a vertical gradient [10-14] and a constant region of value 4.

There are potentially many different ways to decompose any given array (in the extreme case, you can always divide it into $n$ by $m$ constant single-cell regions), so I'm interested in finding a 'simplest' solution (i.e. one with as few regions as possible.)

Has this problem been studied or is it related to another kind of problem that has been studied?  It seems like it could be approached using some sort of tree representation where I start with all cells as individual constant regions, then combine them together under larger regions as long as they meet the desired constraints, then evaluate using some fitness function to decide whether it is an optimal (or at least 'good enough') decomposition.

Regarding the optimality constraint, I have some flexibility here, so I can choose a constraint that helps make the problem easier to solve.  Ultimately the goal is to have a decomposition that appeals to human sensibilities of the 'patterns' present in the data, so my first thought is that minimizing the number of regions is probably a good constraint.

Some interesting boundary cases to consider:

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

The preferred decomposition here would be three constant 2x2 regions of '1' and three constant regions of '0'.  This is preferable to the alternate 6 region decomposition with three 2x2 '0-1' gradients and three constant '1' regions, as constant regions are preferable to gradients if the number of regions is the same.

$\begin{bmatrix}1 & 2 & 3 \\ 2 & 2 & 2 \\ 3 & 2 & 1\end{bmatrix}$

Due to symmetry, this can decompose into either horizontal or vertical gradients.  I don't have any preference in this case for which should be chosen as the decomposition.

Regarding distribution of size, it's probably better to avoid at the minimum 1x2 gradients.  Any array can be distributed arbitrarily into various single cell constant blocks and 1x2 gradient blocks, so this kind of interpretation is not particularly interesting.  In the case where there are no other patterns in a region of the data, I'd rather treat it as single cells, as I can do some post-processing to extract these 'complex' regions and treat them as lookup tables.

Another case:

$\begin{bmatrix}1 & 1 & 2 & 3 & 4\\ 1 & 1 & 2 & 3 & 4\\ 1 & 1 & 2 & 2 & 2\\ 1 & 1 & 2 & 2 & 2\end{bmatrix}$

Here it would be preferable to take the 4x2 '1' region and 2x3 '2' region, with a 2x3 '2-4' gradient region.  The alternative '1-4' gradient is worse because it requires splitting the '1' region into two different regions.


texts:
Several popular machine learning algorithms such as Logistic regression or Neural networks require its inputs to be numeric.

What I'm interested in is how you make these algorithms work on non-numeric inputs (such as short strings).

As an example, let's say we're building an email classification system (spam/not spam), where one of the input features is the sender address.

To be able to use a learning algorithm, we need to represent the sender address as a number. One way is to simply number the senders 1..n. Our training set might then look like this:

This won't work, however, because algorithms such as Logistic regression or Neural networks learn patterns in the input data, while in our example, the output looks totally random to the algorithm. Indeed, once in a university class, we tried to train a Neural network on a dataset that looked like this and the network was unable to learn anything (the learning curve was flat).

Would you use Logistic regression or Neural networks in this example at all? If yes, in which way? If not, what would be a good way to classify emails based on sender address?

A perfect answer would discuss the email classification example as well as handling short strings in ML in general.


texts: Partitioning a boolean circuit for automatic parallelization

texts:
tl;dr: I have a problem where I have a Boolean circuit and need to implement it with very specific single-thread primitives, such that SIMD computation is significantly cheaper after a threshold. I'm trying to optimize the implementation.
Going into detail, the input is a combinatorial Boolean circuit (so no loops, state, etc.). I'm implementing it in software with a rather unusual set of primitives, such that:

logic gates must be computed one at a time, as the "engine" is single-threaded
NOT gates are free
AND, OR, XOR have a cost of 1 (eg. 1 second)
N identical gates can be evaluated at the same time for a cost of 10 plus some tiny proportional term (eg. a batch of 20 distinct AND gates can be evaluated in 10 seconds, 50 distinct XOR gates in ~10 seconds, etc.)

The objective is to implement the circuit with the given primitives while minimizing the cost.

What I tried
This problem looks vaguely related to the bin packing problem, but the differences - constraints on the order of the items and different cost for each "bin" depending on the number of items - make me think it's not particularly applicable.
I was suggested to use integer linear programming, which sounds like the best fit so far, but I'm not sure how to represent the problem. Specifically, I'd use binary variables to represent whether the implementation gate/batch M is used in place of the circuit gate N, but then I don't know how to express the objectives to be maximized/minimized.


texts: Proving that the halting problem is not Turing-reducible to the acceptance problem for Turing machines

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

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


texts: Floating point normalised numbers in binary

texts:
Many text books state that for a binary floating point representation in a computer byte, that if the mantissa is normalised,  then a positive number must start with 01 from the left or a negative number with 10 from the left.This is nothing to do with IEEE standard but a common statement in English A level computing books. (A levels are the school leaving exams in most of the UK, and some other countries.)

They then ask you to spot normalised representations:

1) 100000000

2) 011111111

3) 110000000

In the rule above 1 and  2 would be normalised but not 3.

Why does it have to be 10 and 01? How is this rule derived?


texts: What's the name of this multiparty problem?

texts:
Suppose I have $k$ players $P_1,\dots,P_k$ that can communicate with each other directly by sending messages.

For defining the inputs, we consider a fixed set of names $N$ which are integers in $[1,k^2]$.
The input of each player $P_i$ consists of a unique name chosen from $N$ and a set $X_i$ of (up to $k-1$) other integers from $N$. Note that some elements of $X_i$ might refer to names that have been assigned to other players while others are just arbitrary names that weren't assigned to anyone. Each player $P_i$ only knows its own name and its own input and has no idea regarding the inputs and names of the other players, but it can communicate with every player $P_j$ by sending a message to $P_j$ (even without knowing $P_j$'s name).

The goal of the players is to discover at least one of the name (if it exists) that is part of the input set $X_j$ of some player $P_j$ but does not refer to a name assigned to one of the players.

A trivial algorithm for this would simply be each of the $k$ players sending their names and name-sets to $P_1$ and $P_1$ can compute the answer, requiring $O(k^2\log k)$ bits in total.

Intuitively, we could think of the $k$ players as a group of people each of whom knows a list of other people and they would like to discover the name of at least $1$ person who is not part of this group.

Is there a name for this problem of finding the "odd guy out"?


texts: Sequence of N operations Amortized Analysis

texts:
A sequence of $N$ operations is performed on a certain data structure.

The $i$-th operation costs $i$ if $i$ is a power of 2, else it costs 1.

How can I calculate the amortized cost for every operation using the potential function method?


texts: Finding all integer points on a hypersurface

texts:
Given a function $f$ of $n$ variables, is there a reasonable way to generate all integer points on the hypersurface given by $f(x)=0$?

To be more specific, let us assume that $f$ is a polynomial with integer coefficients and $S=\{x\in\mathbb{R}^n\mid f(x)=0\}$ is bounded. If one knows a bound for the elements of $S$, say, if $S\subset [a,b]^n$ for some $a,b\in\mathbb{Z}$, one can simply iterate over all points $x\in [a,b]^n$ and check whether $f(x)=0$. This approach is insanely inefficient.
One way to reduce the number of operations is to iterate over $(x_1,\ldots,x_{n-1})\in[a,b]^{n-1}$ and solve for $x_n$ (numerically and then checking for the nearest integers or by means of the rational root theorem).
One could imagine that there is a way to "move along a hypersurface", that is, only look at the points that are close to $S$. If one has a point $x$ which is close to $S$, it is likely that a point $y$ next to $x$ is close to $S$ as well. So one can move to such a point $y$ and repeat. But not if $y$ gets too far from $S$ (this can be judged by the value $f(y)$, and the gradient of $f$ at $y$ must be taken into account). This, however, requires storing all the integer points already visited, so might take quite a lot of memory (which I would like to avoid). I think this is not trivial even for a plane curve. It there a known way to minimize the number of points visited? In a sense, this look quite similar to the problem of enclosing $S$ inside an "integral envelope", a minimal integral polyhedron which contains $S$ (possibly non-convex and not simply-connected).
To narrow this down even further, let us assume that $f$ is qudratic (and positive-definite), so $S$ is an ellipsoid. I would guess that this particular case is much easier and has been studied before. Any references?
More generally, one can consider unbounded hypersurfaces. Then the problem of visiting all integer points should be reformulated as the problem of walking along the hypersurface and eventually visiting eash integer point (instead of, say, getting stuck on a subvariety).


texts: What is the Number of epochs with no improvement after which training will be stopped.?

texts: I am trying to make a Convolutional neural network. Training the images of different brands of Logos. Have 100 images per class and there are 40 classes. I have trained the model now want to check that model is overfitted or not . What should be the number of epochs we will se that with no improvement after which training will be stopped . Should I see after 2, 3 or which number ?


texts: What is the first programming language where the keyword "new" appeared?

texts: It's really interesting when this keyword first appeared as a lot of popular languages but relatively old languages( C++, C#, Java, JS ) use it. I understand use of "new" in C++ in practical manner( stack vs heap ). But i don't understand it in Java, Js, C# where all objects( except C# structs ) are created on heap by default.


texts: How to prove LastToken problem is NP-complete

texts:
Consider the following game played on a graph $G$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding one token to some neighboring node. The LastToken problem asks whether, given a graph $G$ and an initial number of tokens $t(v) \ge 0$ for each vertex $v$, there is a sequence of moves that results in only one token being left in $G$. Prove that LastToken is NP-complete.

I'm learning how to prove NP-complete recently but having trouble to understand the concept of NP. As far as I know, to prove a problem is NP-complete, we first need to prove it's in NP and choose a NP-complete problem that can be reduced from. I'm stuck on which NP-complete problem that can reduce to my problem. As I interpreted this is sequencing problem and I'm guessing I can either reduce Ham Cycle or Traveling Sales Man to my problem, but I don't see any connection between them so far. How should I start a good approach?


texts: How to initialize the first h in an RNN?

texts:
Take a Vanilla RNN represented by the function $h_t = f(h_{t-1}, x_t)$, how do you determine $h_0$?

Edit: This answer over on the stats page has helped.


texts:
This is a school assignment, I am fairly new to DFA's.

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

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

Translating L:

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

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

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

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


texts: Does "not regular" imply "acceptor needs memory"?

texts: Regular Languages, by definition, can be accepted by finite automata, which do not have memory. But if I know that a language is not regular, does that imply that any mechanism that recognizes the language must have memory?


texts: Showing party invitation problem is np-complete

texts:
Suppose you and your $k - 1$ housemates decide to throw a party. Each housemate $i$ gives you a list $P_i$ of people she would like to have invited to the party.  Depending on how much you like housemate $i$, you pick an integer $m_i$ indicating the minimum number of people on $i$'s list that you'll invite.  Having selected these values $m_i$ already, you'd like to know whether it is possible to invite at most $n$ people to your party such that for each housemate~$i$, at least $m_i$ of the people in $P_i$ are invited.  We call this the Party Invitation problem.  Prove that Party Invitation is NP-Complete.

I am not really sure which problem to reduce from and how to construct the reduction. Thank you


texts: Can someone explain the language L = {w: w = uu, u \in La(1*01*)}

texts:
I need help understanding the language L above.

These are my understanding:
- w = uu is a concatenation of u
- La(1*01*) can be expressed in regular language i.e. r1 = 1*01* so La(r1)
- also we have regular expression property of concatenation: L(r1r2) = L(r1)L(r2)

So base on my understanding the language L can be simplified to

I'm not quite sure about this.


texts: What's the difference between a binary search tree and a binary heap?

texts: These two seem very similar and have almost an identical structure. What's the difference? What are the time complexities for different operations of each?


texts: Identifying a starting point for maximum coverage

texts:
I have 10,000 sequentially numbered items I wish to characterize. For each item, I created a list of the other items I think might have a similar characteristic.

i.e.

Item 1: [2,4,7,8,9,...,9489] (list contains 250 items)
Item 2: [1,4,13,23,...,9424] (list contains 12 items)
Item 3: [1,2,4,7,...,9489] (list contains 140 items)
Item 4: [1,3,7,9,...,9211] (list contains 250 items)
Item 5: [1,3,7,9,...,9221] (list contains 250 items)
Item 6: [1,2,7,25,...,9248] (list contains 241 items)
Item 7: [4,5,6] (list contains 3 items)

If I only have time to test 50 items, How might I choose which items to test so that the maximum number of items is represented? The identified similarity is not necessarily bi-directional - notice item 7's list contains 4,5,6 but not 1 and 3(which both have 7 in their list).

Some lists may be very similar or even identical, as seen in items 4 and 5. Testing both 4 and 5 would not achieve the maximum coverage.


texts: LL(k) Prediction Techniques (and Insight on method applied)

texts:
I'm requesting references for LL(k) in situations where k > 1 for reasons described below.

I'm looking for research/notes/anything involving LL(k) predictions.

Any time I look up LL(k) I end up with the description starting about LL(k) and focusing on LL(k) where k = 1.

Is there a formal description for the process to predictions where k can be greater than one, sometimes even as high as 7 to 15?  Granted I can't vouch for or against the performance implications of the k being so high as that, but I just wanted to know if there's been any literature on the subject.


texts: How can I make automaton that has given language?

texts:
I am trying to solve above question, below is the automaton I came up with:

Is there any ways to define automaton without having marked states?


texts: Is this decidable language a subset of this undecidable language?

texts:
I think I understand the theoretical definition of decidable and undecidable languages but I am struggling with their examples.

A(DFA) = {(M, w): M is a deterministic finite automaton that accepts the string w}

A(TM) = {(M, w): M is a turing machine that accepts the string w}

I know that A(DFA) is decidable and A(TM) is not. But, is A(DFA) a subset of A(TM)?


texts: How do balancers work in the context of counting and balancing networks?

texts:
I was learning what balancing networks are and at some point the art of multicore programming talks about balancers. The text book says:

  A balancer is a simple switch with two input wires and two output
  wires, called the top and bottom wires (or sometimes the north and
  south wires). Tokens arrive on the balancer’s input wires at arbitrary
  times, and emerge on their output wires, at some later time.
  A balancer can be viewed as a toggle: given a stream of input tokens, it
  sends one token to the top output wire, and the next to the bottom,
  and so on, effectively balancing the number of tokens between the two
  wires

from the discussion above it would seem that a balancer simple has a state up and down and it alternates between them and send tokens up and down (depending what state it is). Consider how the figure in the textbook defines a balancer:

It says that no matter the order and time, the tokens are split (balanced) as equal as possible between the above wire and the bottom wire. Therefore, no matter how the wires arrive, the balancer should maintain the invariant that the difference between top and bottom is at most 1.

The issue that I have is that it seems to describe the balancer as a state machine than alternates between up and down, but such a machine wouldn't actually be able to properly balance. It has to have some sort of state counting how many tokens it has sent up and how many it has sent down (so that it can balance).  The code presented by the book seems to do the alternating up and down (unless I misunderstood it):

It doesn't quite have a counter than makes sure that it maintains, the balancing invariant. If not, then how does it actually do it?


texts:
$Can$ $a$ $TLB$ $hit$ $lead$ $to$ $a$ $page$ $fault?$

My answer is yes, as say even after a TLB hit if the page in the memory is dirty and it will lead to Page fault. Other case can be that, it is read only and we want to write that page which will eventually lead to page fault.

Now wrt this context, let me ask u question that was asked in GATE 2020 exam(India's one of the most prestigious examination to get into $IIT's$ for Masters and PhD). I know this is not a question ans posting site, but for the sake of clearing my doubt I have to, and the concept can be understood well through this question. The questions goes like this-->

  Consider a paging system that uses $1−level$ page table residing in
  main memory and a TLB for address translation. Each main memory access
  takes $100 ns$ and TLB lookup takes $20 ns$. Each page transfer
  to/from the disk takes $5000 ns$. Assume that the TLB hit ratio is
  $95%$, page fault rate is $10%$. Assume that for $20%$ of the total
  page faults, a dirty page has to be written back to disk before the
  required page is read from disk. TLB update time is negligible. The
  average memory access time in ns (round off to $1$ decimal places) is
  _______.

There is a lot of fuss going around this question as the answer provided by the exam authority is claiming it to range from $154.5ns$ $to$ $155.5ns$, but many fellow scholars are claiming that it should be $725ns$ as there can still be page faults if there are hit in the TLB. Moreover this question is of $2$ marks. So its correctness can change the life of many students.

Your suggestion matters. Whole India is looking for your help.

Thank you.


texts: Is there a way to reflect small edge-weight changes after computing Floyd-Warshall on a large graph?

texts:
I am working on a hex-based game in which I'm trying to pre-calculate pathfinding for a given map using the Floyd-Warshall algorithm. The map size is on the order of thousands of hexes (so maximum tens of thousands of edges).

The map represents an arena in which two teams fight, and both have the ability to change the map, either by creating complete walls (removing a vertex from the graph), or changing weights on the edges (i.e. by temporarily making a hex difficult to walk over).

The reason I'm considering using all-pairs-shortest-path algorithm is because I need to simulate the game as fast as possible, and thus I can't waste time with actual pathfinding during the simulation.

Is there a way to detect which paths need to be re-calculated when a change is made to the graph? It seems that if I only increased the weights/removed vertices, I could only re-calculate the affected paths, is that true? And what if I'm also decreasing weights/adding new vertices/edges?


texts: Method to change value in a key for a min heap

texts: How would you write a method to change the value of a min heap where bool changeKey(int oldKey, int newKey). The keys are unique, no duplicate keys are permitted. If there is a key in the heap with value oldKey, and no existing entry with key newKey, it will change it to newKey, keeping the the heap properties and returning true. If there is no key in the heap with value oldKey, or an existing entry has value newKey, then it will take no action and return false. Also an auxiliary  map is used to store the locations of the keys in an array. I know how to write methods for insertion but haven't seen any implementations of this.


texts: prove upper bound of the recurrence $ T(n) =T(n-\sqrt{n})+1 $

texts: i want to prove  upper bound of the following recurrence $ T(n) =T(n-\sqrt{n})+1 $ is $ O(\sqrt{n})$.


texts: Shortest path in a graph where edges are forbidden depending on the path taken

texts:
I have a problem similar to Shortest path problem where edge weight depends on path taken but not quite the same. In my case each edge has either a fixed finite weight, or an infinite weight, depending on which path has been followed. So depending on the path taken through the graph, some edges from the current node are not allowed while others are. My graph is a DAG otherwise.

The shortest path can consist of many edges so I can't really represent the path history in the graph by duplicating nodes otherwise the number of nodes would increase exponentially and would be intractable.

Would Dijkstra's algorithm for finding the shortest path between two nodes still produce the correct answer in this particular type of graph? What else can I do?


texts: (Possibly Easy) Formal Language Question

texts:
I am looking at a "practice test" for a Theory of Computation class.  It was a test in a previous year.

I am asked to prove that, given L1 and L2 are regular, the union and difference are both regular.

It seems to me that for the union, since all the members of each separate set are regular, and the union consists exactly of all those members, therefore the union is regular.

And since the difference (L1-L2) is just a subset of L1, it is also regular.

This seems awfully straightforward and skips a lot of process.

Is it correct or am I missing something?


texts: Can all Turing-computable problems be solved with a machine with finite tape and infinite controls?

texts: We know all computer computable problems can be solved using the infinite tape and finite control system of the turing machine. Now think something different, let the tape is finite but the control system is infinite. Now can we solve the same set of problems with this machines?


texts: Access to publicly available project with all the artefacts (files) created during the development

texts: Does anyone know where I could get an access to a project that contains all the artefacts (documents) that were created during the development? So I would like to get all the word, pdf, power designer, etc. files as well as all the source code. If possible, I would prefer that all this files are stored in some of the software reporitories.


texts: Is there a formal way of defining a Zeno Machine?

texts:
The idea of a Zeno machine is pretty interesting to me, but I can't seem to find a formal definition for how a Zeno machine would work.  I can find a couple of definitions around but they are all about the same (I suspect that everyone is cribbing off of each other) and lack any real formalism.  A fairly representative definition is this one from the relevant wikipedium

  More formally, a Zeno machine is a Turing machine that takes $2^{-n}$ units of time to perform its $n$-th step; thus, the first step takes $0.5$ units of time, the second takes $0.25$, the third $0.125$ and so on, so that after one unit of time, a countably infinite (i.e. $\aleph_0$) number of steps will have been performed.

This definitions is a little weird.

The biggest reason this definition is lacking is that the description doesn't really tell us anything about the state of the machine at any time $t \geq 1$.

Now if we look at an example of some psuedo-code for an accelerated Turing machine we have a bit of a conflict. Here is a sample slightly modified from C. Calude, L. Staiger. A Note On Accelerated Turing Machines

begin program
  write 0 on the first position of the output tape
  set i = 1
  begin loop
    simulate the first i steps of T on w
    if T(w) has halted,
    then
      write 1 on the first position of the output tape
    set i = i + 1
  end loop
end program

Now this sample is intended to solve the halting problem on a Turing Machine.  And according to the authors:

  By inspecting the first position of the output tape we need one unit of time to run the above machine in order to decide whether $T(w)$ stops or not

Now here we are relying on some notion of the state of the machine at time $t=1$, which is out of the scope of our definition.

Now the intuitive patch here is to say that the state at time $t=1$ is just the limit of the states as time approaches $1$.[1]  But there are some problems with this the most important being that not all sequences will converge.  Take for example the following pseudo-code:

begin program
  set i = 1
  begin loop
    write i on the first position of the output tape
    if i is 1,
    then
      set i = 0
    else
      set i = 1
  end loop
end program

The sequence of states here cannot converge (regardless of how we choose our metric) and thus this naïve patch does not completely fix the problem.

Is there a way of defining a Zeno machine that is formal and complete?

[1] : In fact while I was putting this question together I found this paper which pretty much outright states this definition.


texts:
I enjoy reading research on satisfiability, but sometimes it's easier to find relevant information when you know the names of the variants.

Example:

All the clauses are width 3 and must have exactly 1 true literals and 2 false literals: 1-in-3 SAT
Each clause of width n must have exactly 1 true literal and n-1 false literals: 1-in-k SAT

I'm looking for any of these, if they exist:

Each clause must have exactly x true literals (x not always equal to 1)
Each clause can have at most (or at least) x true literals
Each clause has a number of true literals contained in an interval


texts:
We can write inductive types in terms of a fixpoint type:
Fix : (* -> *) -> *
In : (f : * -> *) -> f (Fix f) -> Fix f

NatF r = () + r
Nat = Fix NatF
Z = In NatF (InL ())
S n = In NatF (InR n)

But this fix type is not sufficient for indexed datatypes and we need an indexed fixpoint:
IFix : (I : *) -> ((I -> *) -> (I -> *)) -> I -> *
IIn : (I : *) -> (F : (I -> *) -> (I -> *)) -> (i : I) -> F (IFix I F) i -> IFix I F i

FinF r n = (n = Z) + ((m : Nat) ** r m ** (n = S m))
Fin = IFix Nat FinF

Using IFix we can get Fix back by setting the index type to unit.
What datatypes can we not write using IFix, is there a more general fixpoint than IFix?


texts: Is a subgraph either a spanning subgraph or a full subgraph?

texts:
A graph $G' = (N' ,A')$ is a spanning subgraph of a graph $G = (N, A)$
iff $N ' = N$ and $A' \subseteq A$.
A graph $G' = (N',A')$ is a full subgraph of a
graph $G = (N, A)$ iff $N' \subseteq N$ and $A' = \{(x,y) \in A \mid x,y \in N '\}$.

I have to prove that "If $G'$ is a subgraph of a graph $G$, then either
G' is a spanning subgraph of $G$, or $G'$ is a full subgraph of $G$. If this statement
is valid, provide a proof that it is valid, otherwise provide a counterexample" but isn't a full subgraph actually a spanning subgraph?

I mean that any subgraph of $G$ is a full subgraph in the end, right?
Any ideas how I can prove the statement?

My second question is how to calculate the number of spanning subgraphs of $G$ as a function of the number of nodes in $N$. How can I do this without knowing $A$ or how many edges I have in the graph?