texts:
Let G = (V,E) be a directed graph, where V is a finite set of nodes, and E ⊆ V × V be the set of (directed) edges (arcs). In particular, we identify a node as the initial node, and a node as the final node. Let x and B be two non-negative integer variables. Further, we decorate each edge with one of the following four instructions:
x := x + 1;
x := x − 1;
x == 0?;
x == B?;
The result is called a decorated graph (we still use G to denote it). The semantics of a decorated graph is straightforward. It executes from the initial node with some non-negative values of B and x (satisfying 0 ≤ x ≤ B), then walks along the graph. G can walk an edge (v,v0) if all of the following conditions are satisfied:
• if the edge is decorated with instruction x := x+1, the new value of x must satisfy 0 ≤ x ≤ B.
• if the edge is decorated with instruction x := x−1, the new value of x must satisfy 0 ≤ x ≤ B.
• if the edge is decorated with instruction x == 0?, the value of x must be 0.
• if the edge is decorated with instruction x == B?, the value of x must equal the value of B.
If at a node, G has more than one edge that can be walked, then G non deterministically chooses one. If at a node G has no edge that can be walked, then G crashes (i.e., do not walk any further). It is noticed that B can not be changed during any walk. However, its initial value can be any non-negative integer. We say that a decorated graph G is terminating if there are nonnegative initial values for B and x (satisfying 0 ≤ x ≤ B) such that G can walk from an initial node to a final node. Design an algorithm that answers (yes/no) whether G is terminating or not.


texts: Data-flow analysis problem adjust to Ullman-Aho's framework?

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

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

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

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

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

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


texts: Finding Degree of match with Soundex or Metaphone

texts:
I am working on a search where user would search names. Spelling mistakes are bound to happen. I have used edit distance, soundex and metaphone implementations in java so far. Each one separately and then different combinations too. Finally, a combination of soundex and metaphone seemed to work. There are more than 30 thousand names that would be searched for the match when ever a user enters a name. The search is sequential and would stop when ever a match is found. Now the problem is. Lets say in fol figure:-

   User Input Name = "Peeter"

----------------------------------------------------
 Serial       Name
----------------------------------------------------
   1           Tom
   2           Petay (Near match say 70%)
   3           Jack
   4           Peteh (Near Match say 75%)
   5           Peter (The closest Match say 100%)
----------------------------------------------------

The closest match for "Peeter" is "Peter" and near match is "Petay", "Peteh" etc. The search would stop at "Petay", returning "Petay" as the name which would be least expected by the user. So for me, 2 solutions comes to mind.

Search all 30 thousand names every time, get a list of all matches and ask user to choose the best match
Secondly, present 3 or say 5 top matching (by top matching i mean the closest match, let say more than 90% similar sounding) names to user.

I already have implemented option 1 but it returns some times more than 100 matches! it would not be possible for the user to go through all of them. So is there any way to implement option 2 mentioned above? i.e to find out to what degree soundex or metaphone match is made to a name.

Thanks in advance.


texts: Reduction from partition to multiprocessor scheduling

texts:
I am kind of unsure about a reduction between two problems.
Here are the two problems:

PARTITION:
Instance: A finite set of n positive integers $S= \{a_1,a_2,...a_n\}$.
Question: Can the set $S$ be partitioned into two subsets $S_1$,$S_2$, s.t. the sum of the numbers in $S_1$ equals the sum of the numbers in $S_2$?

MULTIPROCESSOR SCHEDULING:
Instance: A set $J$ of $k$ jobs where job $j_i$ has length $l_i$, and $m$ processors.
Question: Can we schedule all jobs in $J$ on $m$ processors s.t.:
(a) on each processor the next job in the sequence is started immediately after the preceding job is finished and (b) the total time to execute all jobs on each processor takes the minimum possible time $T_{min}=\big(\sum\limits_{i=1}^k l_i\big)/m$

I am a little bit unsure about my try to reduce Partition to multiprocessor scheduling. My attempt is posted as an answer.


texts: Is this language $\{0^n1^m | (n+m) \text{is even}\}$ regular or not?

texts:
$$L=\{0^n1^m | (n+m) \text{is even}\}$$

Using the pumping lemma ,
let me choose a valid string $W=0011$ $(n=2,m=2$ and $4$ is even$)$.
Let the number of states in the DFA ($C$) be $3$ (I find this step to be fishy)
$|W|\ge C$
Let $W=XYZ$
I choose $X=00,Y=1,Z=1$ such that $|xy| \le C ,|Y| \ge1$
So, for all $i$, $00(1)^{i}1$ should be in $L$
But when $i=2$,String $00111$ is not in $L$, hence this language is not regular.

But I came across a regular expression for the same language:

$$0(00)^*1(11)^*+(00)^*(11)^*$$
Is there a flaw in my pumping lemma or the regular expression? Someone please help me out.


texts:
What is the 1's and 2's complement of 0.01101?
I'm unable to find any details on this from google.

Basically how do we represent the floating points in 1's and 2's complement forms?

Even wikipedia only says that 1's complement is the inverted bits of binary representation. The examples only contain integer values. I couldn't find anything clear about what is the exact significance of this system. Hence, unable to deduce if the inverting bits applies to floating points also.


texts: Defining a new (informal) operator in CTL

texts:
If you were given a "new operator" Wh and a formula a Wh b meaning that a holds for at least as long as b does (in all executions). How would you define this operator in CTL? This is an exercise question in the book "Principles of Model Checking" (page 303) if anyone has a copy.

My first thoughts are that I'll definitely need to use the "FOR ALL" quantifier, but I'm not sure where to go from there. So I want to know the thought-process that I should have when dealing with these types of questions more than anything. What I'm looking for is for someone to perhaps give me a walk-through or a very quick guide to solving questions like these.

Thanks in advance for any input.


texts: Better word to describe JavaScript "algorithm"?

texts:
For my undergraduate senior project, a professor asked me and my partner to design an algorithm to determine true resolution in the browser, unaffected by zooming, multiple screens, viewport size, etc. (tl;dr our implementation was okay, it usually did the job correctly.)

It's super pedantic, but I've been thinking about the terminology of calling it an "algorithm". It really doesn't seem like an algorithm, because it's very dependent on JavaScript and the state of the browser at a given time. Particularly, our script has a lot of if-statements to determine what what variables and data to work with depending on the browser and configuration. I certainly don't think I could write it out in a language-agnostic pseudocode.

Is there a better word to describe what we wrote? Does it count as an "algorithm" per say? If I had to think of alternate words, they'd be:

implementation (but of what, just our general idea/design?)
script/program

Are there better words that are more general than simply script or program?


texts: Running time analysis for algorithm that merges $k$ sorted arrays to one sorted array

texts:
Given $k$ sorted arrays, the size of each array is $n$ and we want to sort them to one sorted array. assume that $k=2^p$ i.e $k\in\{ 2^1,2^2,2^3,2^4,\dots\}$
I the first step we will merge (the first and the second arrays),(the third and the fourth arrays),(the fifth and the sixth arrays),... till we get sorted arrays with length of $2n$
In the second step we will merge again each successive pair till we get sorted arrays with length of $4n$

I need to find the time complexity of this algorithem.
What I tried:
I know that merging two sorted arrays one with length $t$ and the other with length $r$ takes $\Theta (t+r)$ .
In this case the length of each array in the first iteration is $n$, so:

In the first iteration: merging each pair takes $\Theta(n+n)$  and there are $k/2$ merges so $\Longrightarrow \frac k 2 \Theta(2n)$

In the second iteration: merging each pair takes $\Theta(2n+2n)$  and there are $k/2^2$ merges so $\Longrightarrow \frac k 4 \Theta(4n)$

In the third iteration: merging each pair takes $\Theta(4n+4n)$  and there are $k/2^3$ merges so $\Longrightarrow \frac k 8 \Theta(8n)$

In the i-th iteration: merging each pair takes $\Theta(2^in)$  and there are $k/2^i$ merges so $\Longrightarrow \frac k {2^i} \Theta(2^in)$

I got stuck here, I know that binary search takes $\Theta (\log n)$ because it divides the array to two in each iteration and here it should be ralated to $\log $ somehow,


texts: Pumping Lemma Question: About the cases for y in the xy^iz criterion

texts:
Problem statement:
Let $\Sigma = \{a, b, c\}$, and consider the task of multiplication encoded in the language $L = \{a^n b^k c^{nk} : n \geq 0, k \geq 0\}$.
Prove that L is not regular using the pumping lemma.

Relevant sources:
Sources (from three different people) arguing in favour of cases (where the links that are videos are set to the exact frame that I want you to see - there's no need to watch the video(s)):

https://youtu.be/dikEDuepOtI?t=393
https://youtu.be/Ty9tpikilAo?t=474
https://youtu.be/g4e2RElzCSQ?t=1282
https://www.physicsforums.com/threads/non-regular-language-pumping-lemma.945301/

My attempted solution:

$L = \{a^n b^k c^{nk} : n ≥ 0, k ≥ 0\}$
Let us choose the string generated when $n = k = P = 2$. That is, let us choose $S = a^2 b^2 c^4$ as a string.
Furthermore, let us assume that $S$ is regular.
Then, we try to make that string be of the form $S = xyz$, and it should meet the criteria of the pumping lemma, which are that
(i) $x y^i z ∈ L$
(ii) $|y| > 0$
(iii) $|xy| ≤ P$
Then, there are six cases, and they are as follows:
I) $y$ only contains occurrences of a.
II) $y$ only contains occurrences of b.
III) $y$ only contains occurrences of c.
IV) $y$ contains occurrences of a and b.
V) $y$ contains occurrences of b and c.
VI) $y$ contains occurrences of a, b and c.
So, for the string $S$ to fulfill the criteria of the pumping lemma, it must be shown that (i), (ii) and (iii) each hold true for at least one of I), II), III), IV), V) and VI). That is, for the string to not fulfill the criteria of the pumping lemma, it must fail at least one of the three parts of the pumping lemma for all six of the above cases.
Case I):
Let $x = a$, $y = a$ and $z = b^2 c^4$. Then, it is indeed the case that $|y| = 1 > 0$ and that $|xy| = 2 \leq 2$. However, if an integer $i = 2$ is chosen, then a string $a a^2 b^2 c^4 = a^3 b^2 c^4 ∉ L$ is obtained. So, case I) fails.
Case II):
Let $x = a^2$, $y = b^2$ and $z = c^4$. Then, it is indeed the case that $|y| = 2 > 0$, but it is not the case that $|xy| = 4 \leq 2$, and so case II) fails. (There is no need to examine part (i) of the pumping lemma.)
Case III):
Let $x = a^2 b^2$, $y = c^2$ and $z = c^2$. Then, it is indeed the case that $|y| = 2 > 0$, but it is not the case that $|xy| = 6 \leq 2$. So, case III) fails.
Case IV):
Let $x = a$, $y = a b^2$ and $z = c^4$. Then, it is indeed the case that $|y| = 3 > 0$, but it is not the case that $|xy| = 4 \leq 2$. So, case IV) fails.
Case V:
Let $x = a^2$, $y = b^2 c$ and $z = c^3$. Then, it is indeed the case that $|y| = 3 > 0$, but is not the case that $|xy| = 5 \le 2$. So, case V) fails.
Case VI:
Let $x = a$, $y = a b^2 c$ and $z = c^3$. Then, it is indeed the case that $|y| = 4 > 0$, but it is not the case that $|xy| = 5 \leq 2$. So, case VI) fails.
Then, because all six cases have failed at least one of the pumping lemma’s criteria, it follows that the language $L$ is not regular.

My teacher's solution:

Assume for contradiction that $L$ is regular and apply the Pumping
Lemma. Let $m$ be the integer in the Pumping Lemma. Take $w = a^mb^1c^m$. Since
$w ∈ L$ and $|w| ≥ m$, we can write $w = xyz$ such that $|xy| ≤ m$ and $|y| ≥ 1$ and
any string of the form $xy^iz ∈ L$ for $i = 0, 1, 2, \dots$ This implies that $y  =a^k$ for some $k ∈ \{1, \dots , m\}$. Taking $i = 0$, we get that $xz = a^{m−k}b^1c^m ∈ L$; however, this
contradicts the definition of $L$, since $(m − k) \cdot 1 \neq m$. Contradiction.

Are we both correct? Is at least one of us wrong? Why?
Any input would be greatly appreciated!


texts:
I have a binary tree with $n$ nodes. The tree is not necessarily balanced.

For each node of the tree, I count down the total number of the nodes for its left sub-tree as $n_L$ and then I count down the total number of the nodes for its right sub-tree as $n_R$. Then I calculate $\min(n_L,n_R)$ and then assign the minimum value as a tag to the node. I repeat this process to produce appropriate tags for all the nodes of the tree.

Now I wonder what is the big O for the sum of all the tags. I mean, I wonder if the sum of tags is $O(n\log n)$ or $O(n)$ or $O(n^2)$.

In the most unbalanced case, the binary tree is just a long list like figure below. In this case, I think sum of tags would be 0, therefore the big O would be $O(0)$.

In the case of a perfect binary tree, the tag of the root node might be $2^0\frac{n}{2^{0+1}}$ and at the next level, i.e. root's left and right children, sum of tags might be $2^1\frac{n}{2^{1+1}}$ and for the $i$th level of the perfect binary tree, the sum of tags might be $2^i\frac{n}{2^{i+1}}$.

At the $i$th level, sum of tags might become $2^i\frac{n}{2^{i+1}}=\frac{n}{2}$ therefore looks like that some of tags at each level might be $\frac{n}{2}$ and because a perfect binary three has a total height of $\log_2n$ hence the total sum of tags might be $\frac{n}{2}\log_2n$ and this implies that for a perfect binary tree, the big O for sum of tags might be $O(n\log_2n)$.


texts:
I've read various descriptions of the TGP, most of which seem vague or conflicting on the precise constraints of the problem. Specifically:

is it always or sometimes impossible to reach consensus
finite/infinite messages required
given unreliable communication, is actual message loss important or not.

As another point, the depiction of the problem seems inadequate, as there's no need
for the generals to always require acknowledgement for their last message if they regard previous ones:
0       A ----time info--> B
1       A <---AckForA0---- B
2       A ----AckforB0---> B
3       A <---AckforA1---- B
1... A knows B received his time info and is ok with it but might not attack if he doesn't receive confirmation for his ack.
2... B knows A received his ack because he responded.
3... A knows B got his ack because he responded
Can anyone give a better example which illustrates this specific need to rely on acks of the respective last messages.


texts: Turing Machine Decidable: What right does the definition have to say what's not in language L?

texts:
I'm having trouble understanding the definition of Turing Decidable. The definition goes something like this:

  TM M decides language L iff the strings in L put M into the Accept state
  and the strings NOT IN L put M into the Reject state

My problem is.. the strings "NOT IN L"? How can the definition be based on what's not in L? Shouldn't the definition be more like this?

  TM M decides language L iff the strings L put M into the Accept state
  or the Reject state.

Then you can divide L into two subsets - those that are accepted, and those that aren't. But they're all decided by M, no?


texts: Are there non-quantum, (potentially) realizable in the real world models of computation that allow a polynomial speedup over RAM?

texts:
I hear a lot about how quantum computers are a big thing because they allow solving some problems in polynomial time which we don't know how to do classically. As far as I understand it still isn't fully proven that they can be built in a scalable way. But what about less dramatic speedups? Could we build a computer that could, for example, find out the longest common subsequence of two strings in linear time or multiply matrices in $O(n^{2+\epsilon})$ time? Is there some physical/metaphysical significance to the RAM model or is it just whatever people first came up with?

Sorry in advance for any false assumptions and problems this question might have, I hope that at least something can be extracted from it that makes sense.


texts:
In recent article of PM the memcomputing is presented. But I did not understand how it works, according to the text.

What is the general principle of work for this memcomputing? How it is done in hard-ware?


texts: Defining $a^n b^{n^2}$ with one existential SO binary relation

texts:
Is it possible to define the language:

$$L = \{ a^n \; b^{n^2} \}$$

  using an existential second order sentence over strings (ordered structures with unary predicates $U_a(x), U_b(x)$) using only one binary relation?

The sentence should have this form: $\exists M ( \exists B_1,...,B_n ( \varphi ))$ where:

$M$ is a binary relation
$B_i$ are monadic
$\varphi$ is first order with signature (available relations) $\sigma = \langle <, U_a, U_b \rangle$

If not, how to prove it? (or cite a textbook in which I can find similar exercises)


texts: For selection in worst-case linear time ambiguity in consideration of $n$ for which $T(n) =O(1)$ and $T(n)\leq cn$

texts:
I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the recurrence relation for analyzing the time complexity of the linear SELECT algorithm and I felt that few things probably mismatch with respect to the range of $n$, the input size for which $T(n)$ is assumes $O(1)$ and $cn$ in the substitution method.
The details of the text are as follows:

We can now develop a recurrence for the worst-case running time $T(n)$ of the algorithm SELECT. Steps 1, 2, and 4 take $O(n)$ time. (Step 2 consists of $O(n)$ calls of insertion sort on sets of size $O(1)$ Step 3 takes time $T(\lceil n/5 \rceil)$, and step 5 takes time at most $T(7n/10+ 6)$, assuming that T is monotonically increasing. We make the assumption, which seems unmotivated at ﬁrst, that any input of fewer than $140$ elements requires $O(1)$ time; the origin of the magic constant $140$ will be clear shortly.$^\dagger$ We can therefore obtain the recurrence
$$T(n) \leq \begin{cases}
        O(1)&\quad\text{if $n<140$ $^\ddagger$} \\
       T(\lceil n/5 \rceil)+T(7n/10+ 6)+O(n)&\quad\text{if $n \geq 140$ $^\|$}\\
\end{cases}$$
We show that the running time is linear by substitution. More speciﬁcally, we will show that $T(n)\leq cn$ for some suitably large constant $c$ and all $n > 0$. We begin by assuming that $T(n)\leq cn$ for some suitably large constant $c$ and all $n < 140$ $^{\dagger\dagger}$; this assumption holds if $c$ is large enough. We also pick a constant a such that the function described by the $O(n)$ term above (which describes the non-recursive component of the running time of the algorithm) is bounded above by an for all $n > 0$. Substituting this inductive hypothesis into the right-hand side of the recurrence
$$T(n) \leq c\lceil n/5 \rceil + c(7n/10+6) +an$$
$$\leq cn/5 + c + 7cn/10 + 6c +an$$
$$= 9cn/10+7c+an$$
$$= cn+(-cn/10+7c+an).$$
which is at most $cn$ if
$$-cn/10 + 7c + an \leq 0.\tag 1$$
$$\iff c\geq 10a(n/(n-70)) \quad\text{when n>70} $$
Because we assume that $n\geq 140$ $^{\ddagger\ddagger}$ we have $n/(n-70)\leq 2$ and so choosing $c\geq 20a$ will satisfy the inequality $(1)$

$$ \dagger \quad \text{The statement here complies with the $\ddagger$ in the recurrence relation} $$
$$ \dagger\dagger \quad \text{The statement here does not comply with the $\|$ in the recurrence relation} $$
$$ \ddagger\ddagger \quad \text{The statement here does comply with the $\|$ in the recurrence relation} $$

I could not quite understand this discrepancy, however I did not include the entire algorithm (available in CLRS Section $9.3$) but if incase it is needed please say then I shall include it as well.


texts:
Let's say you have $n$ symbols. You can encode a $\log_2(n!)$-bit message by permutating the symbols. I will call this a permutation code (if you have seen this concept before, I would love to see a reference).

Let's say we are encoding a message with $k<\log_2(n!)$ bits. It is possible to add error correction. One way is to simply add any old error correction scheme to the string before applying the permutation code. I'm wondering if there is a way that is optimal for permutation codes.

In particular, is there some way of doing a permutation coding that is resistant to transpositions (in terms of error detection and correction)?  I want something that will tolerate up to $t$ transpositions of adjacent symbols.


texts:
This question is motivated from this post. Let $G$ be a given graph, for each vertex $v \in V$, I will label $v$ with $Triangle(v)$.

$Triangle(v) : $ means number of distinct triangles contain $v$.

Question : Is it a valid canonical form? Is computing this function easy (mean polynomial time)?


texts: Don’t understanding argument on words of a certain form

texts:
In my book they use the following argument which I don’t understand :

  Let $L$ be a langage such that there is $m_1, ..., m_k \in \Sigma^*$ such that $ L \subset m_1^*...m_k^*$. Now choose the minimum $n$ such that there exists $l_1,..., l_n$ such that every word of $L$ is a prefix of a word in $l_1^*...l_n^*$.
  Hence by the minimality of $n$ there exist a word $u \in L$ such that $u$ is not a prefix of a word in $l_1^*...l_{n-1}^*$.

What I don’t understand is why such an $u$ exist. I don’t see why the minimality of $n$ prove the existence of such an $u$...
For example if I take $L = ab^*c^*d$ then I think the minimal $n$ is $4$ with the words $l_1 = a, l_2 = b, l_3 = c, l_4 = d$ and in this case such an $u$ clearly does not exist.

So is my book wrong or I am completely missing something here ?

Thank you !


texts: What exactly is the difference between a Balanced Binary Search Tree and an AVL tree?

texts:
I'm learning some Data Structures and I cannot figure out the difference between the Balanced BST and the AVL Tree. From my understanding, an AVL tree is a balanced tree with the height difference <= 1.
But then what about the Balanced Binary Search Tree? What's the difference here?
Let's take an example:
I have a sorted array X = {1,2,3,4,5} and if I insert each of the values in X into a Balanced Binary Search Tree, I get the PreOrder output as 3 1 2 4 5. However, if I insert each of the values of X in an AVL tree, I get the PreOrder output as 2 1 4 3 5.
I notice that an AVL is always self-balancing, but it seems that a balanced BST is not necessarily an AVL.
I am quite confused about this. Is there something I am missing here?


texts: Turn words array from a document with their coordinates into sentences

texts:
I have an array of words with their coordinates in the document, I want to turn them into sentences.
For example this:

  [
    {
        "bounds": [
          {
            "x": 10,
            "y": 10
          },
          {
            "x": 15,
            "y": 10
          },
          {
            "x": 15,
            "y": 15
          },
          {
            "x": 10,
            "y": 15
          }
        ],
        "desc": "Hey"
      },
    {
        "bounds": [
          {
            "x": 18,
            "y": 10
          },
          {
            "x": 24,
            "y": 10
          },
          {
            "x": 24,
            "y": 15
          },
          {
            "x": 18,
            "y": 15
          }
        ],
        "desc": "Name"
      },
          {
        "bounds": [
          {
            "x": 18,
            "y": 20
          },
          {
            "x": 24,
            "y": 20
          },
          {
            "x": 24,
            "y": 25
          },
          {
            "x": 18,
            "y": 25
          }
        ],
        "desc": "What"
      },
    {
        "bounds": [
          {
            "x": 18,
            "y": 20
          },
          {
            "x": 24,
            "y": 20
          },
          {
            "x": 24,
            "y": 25
          },
          {
            "x": 18,
            "y": 25
          }
        ],
        "desc": "Sup"
      }
]

Should Have turned into this:

Hey Name
What Sup

The coordinates are not accurate just an example, also the algorithm needs to deal with words that are in the middle of sentences and other extreme cases.

What it the best way I can do it (Ideally implemented with JavaScript)?


texts:
Consider a (smooth) function
\begin{align*}
F: \mathbb{R}^2 \to \mathbb{R}
\end{align*}
with the contour
\begin{align*}
\mathcal{C} = \{x \in \mathbb{R}^2 | F(x) = 0\}
\end{align*}
The function (and possibly derivatives) will be given as analytical expression, and be continuously differentiable everywhere. I am trying to find an algorithm that takes two points $x_1, x_2 \in \mathcal{C}$ that are numerical roots of this function and tells me, if they lie on the same connected component of $\mathcal{C}$ (or maybe some more general set). I am a little lost here. I found some info on a (pretty complicated) algorithm that seemingly would allow me to first construct a graph representing $\mathcal{C}$ with accurate topology, and then I could just check to which connected component my points belong.

However, I don't fully understand the algorithm and it seems a little overboard for what I want to do. Does anyone know of an easier/faster algorithm to achieve this? Will I have to compute the full contour to solve this?

Edit: In case I really have to compute the full contours (or at least trace part of them) and there is no shortcut, my question would be: How can I compute the connected components of the contour? All sources I stumble upon already require me having a graph that encapsulates the correct connectedness informations and tracing seems problematic without any reliable "test" to find out if two points (e.g. one before and after some tracing step) are indeed on the same component. Ideally I would like an algorithm that constructs a function, say $G:\mathcal{C} \to \mathbb{R}$, such that $G(a)=G(b)$ iff $a$ and $b$ lie on the same connected component.


texts: Finding (and possibly extracting) source code in heterogenous text data set

texts:
I'm looking for a way to recognize and possibly extract source code from text files that may contain only source code, source code mixed with plain text or just plain text without any source code.

There's different source code contained in the data set, just to name a few examples: Java, C, Python, Bash, PHP, Javascript, ...

An example of a mixed file would look something like this:

Title
=====

Introduction
------------
dolor sit amet, consetetur sadipscing elitr, sed diam
nonumy eirmod tempor invidunt ut...

Description
-----------
Labore et dolore magna aliquyam erat, sed diam voluptua:

    [.c snippet]

At vero eos et accusam et justo duo dolores et ea rebum.

Proof of Concept
----------------
Stet clita kasd gubergren, no sea takimata sanctus est
Lorem ipsum dolor sit amet.

-- sourcefile.c --

[Full .c source file]

The above is only an example and while there might be some files with similar layout, most of them differ quite a bit.

Only looking for one specific language would be preferred, but not required.

My first naive approach when looking for Java source code was to run a simple keyword search using Java keywords, but the results weren't that great. Most java keywords are neither unique to java nor sparingly used in plain text, so what turned up as top results was mostly C files, and of course, this doesn't tackle extraction at all.

I recognize that this is a difficult problem, and I've had no success googling for this topic. The most interesting thing I've found was this paper titled Extracting Code Segments and Their Descriptions from Research Articles, but it's not quite relevant since it's much more focused on the Descriptions part than it is on the Code Segments part.

Is there some kind of algorithm or existing program or library that solves this or a similar problem? Or maybe some kind of neural network flavor?


texts: Number of words of length n for special language

texts:
Let $\Sigma$ be an alphabet and let $L$ be a language over it with the following properties:

if $w\in L$ then there exists $v\in \Sigma^*$ such that $wv \in L$ and for every $s\in \Sigma$ the word $wvs$ does not lie in $L$
$wv\in L$ then $vw \in L$
It is prefix-closed,  i.e. prefix of any word is still in the language.

Note that by the definition, it is not cyclic language. I'm trying to compute its growth function, by that I mean $\gamma_n:= |\{w\in L \mid |w| = n\}|$. I know about my specific case that it is not regular and my hypothesis is that function $\Gamma(x) = \sum_{n=1}^\infty \gamma_nx^n$ is not rational. However, I couldn't find any information about these functions for non-regular languages. Maybe, there's a formula that connects entropy of language, i.e. $e(L):= \limsup\limits_{n\to\infty} \frac{\log\gamma_n}{n}$ and the $\Gamma$ function. Or for such a language there's a way to describe its growth throughout the growth of the language $\operatorname{End}(L) = \{ w\in L \mid \forall s\in \Sigma \,ws \text{ is not in } L \}$.


texts: On-line simulation of a two-head tape Turing machine using single-head tape(s)

texts: I have a question and I haven't been able to figure out the answer yet. I need to do the on-line simulation of a two-head tape Turing machine using single-head tape(s). I've found some online articles for the fact that one single-head tape doesn't suffice for this problem and the simulation should be done using two single-head tapes, but I haven't been able to present an accurate simulation of two-head TM using these single-head tapes. Are there any thoughts on how to do so? Thanks,


texts: Would creating a complete computer simulation of the human brain prove the Church-Turing thesis?

texts:
According to Wikipedia, the Church-Turing thesis "states that a function on the natural numbers is computable by a human being ignoring resource limitations if and only if it is computable by a Turing machine."

If we made a complete simulation of the human brain, that would imply that a Turing machine can do everything that a human brain can do. Wouldn't that prove the thesis?


texts: Which method for ODE instead of Euler's?

texts: I need a super-fast method for ordinary differential equations. Should I use the midpoint method? I need this for a reaction-diffusion system (Gray-Scott).


texts: If a Language is Non-Recognizable then what about its complement?

texts:
Is the complement of a Non-Recognizable language

Recognizable
Non-Recognizable
May be Recognizable, May be Non-recognizable. I.e cant comment.

A mathematical proof would be of great help since im unable to think of any way to prove this.

I did some research on this and found below examples. Im specifying complement using a "!"

!A(TM) is a non-recognizable language while A(TM) is a recognizable language.
EQ(TM) is a non-recognizable language and !EQ(TM) is also non-recognizable language

The above two would mean that we simply cant comment on the Recognizability of the complement of non-recognizable language. But I feel that there should be some way to prove (or disprove) this.


texts: "Famous logicians have made embarrassing errors here," a line from SICP. What is this referring to?

texts:
Here is the context (Structure and Interpretation of Computer Programs, section 1.1.8, under heading "Local names"):

  A formal parameter of a procedure has a very special role in the procedure definition, in that it doesn't matter what name the formal parameter has. Such a name is called a bound variable, and we say that the procedure definition binds its formal parameters. The meaning of a procedure definition is unchanged if a bound variable is consistently renamed throughout the definition.

At the end of that last line, there is a footnote (26), which says:

  The concept of consistent renaming is actually subtle and difficult to define formally. Famous logicians have made embarrassing errors here.

What or who is the text referring to? Why would defining "consistent renaming" be hard, which logicians have made errors trying to define this, and what were those errors?


texts: Understanding compression/encoding in linear time

texts:
I'm reading the paper N. J. Larsson, A. Moffat: Offline Dictionary-Based Compression, which describes a compression algorithm that, if I understand it correctly, is quite similar to Byte pair encoding.

Given a string $S$ of length $n$, I'm trying to understand how one can compress it in linear, $\mathcal O (n)$, time with this compression method. How exactly is this done? I've read the paper, but I still don't understand how they achieve linear time, so maybe I would understand it explained in a different way.

My first confusion arises in the first step in the algorithm, where we find the most common pair, e.g. in abcababcabc the most common pair ab would be replaced by a new symbol, say XcXXcXc. I don't understand how we can find the most common pair quickly enough. My naive approach would be to look first at the first pair ab and then count the number of occurrences, then look at the next pair bc and count the number of occurrences, etc. However this would already give $\mathcal O (n^2)$ just for finding the most common pair once.

Next, even if I understood how to find the most common pair in $\mathcal O(n)$ time. My next problem is that, don't we have to find the most common pair up to $\mathcal O(n)$ times? And hence this would give a total time of $\mathcal O(n^2)$?


texts: Efficient compression of unlabeled trees

texts:
Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $T$ and replace all pointers to $T'$ with pointers to $T$. See uli's answer for an example.

Give an algorithm that takes a tree in the above sense as input and computes the (minimal) number of nodes that remain after compression. The algorithm should run in time $\cal{O}(n\log n)$ (in the uniform cost model) with $n$ the number of nodes in the input.

This has been an exam question and I have not been able to come up with a nice solution, nor have I seen one.


texts:
I'm developing a IMHO very interesting algorithm for integer division. This algorithm uses boolean shifting(It shifts left for multiplication by 2). I'm wondering if << c is $O(c)$ or $O(n)$. I'm hearing it depends on architecture. Algorithms ideally should be architecture independent. So for the purposes of analysing the time complexity of my algorithm, should I consider << c as 1 primitive operation or c primitive operations.

I've looked at the other questions here, and they are saying it depends on the machine.

I'm using RAM model of computation, but don't want to assign << c a cost of 1 when it may in fact cost c.


texts:
Given a connected graph, with weighted edges, a virus starts from a given node. It takes x seconds for the virus to travel from a node to one of its neighbours where x is directly proportional to the weight of the edge.
If you are allowed to remove one edge from this graph in order to maximize the ammount of time it takes for the virus to infect all the nodes. How to find this edge?
I could come up with an $O(E\cdot(V+E))$ solution to remove every edge one by one and then run BFS to find out the time it takes for the virus to infect every node. Is there a better solution in terms of time complexity?
This challenge was asked in one of the codenation interviews. It is mentioned in this interview experience: https://www.geeksforgeeks.org/codenation-interview-experience-full-time-sde-off-campus/


texts:
Rice-Shapiro theorem states that

  version A

  Let $\Gamma$ be a set of computably enumerable sets, and $I = \{e : W_e \in \Gamma\}$ its index set in some admissible enumeration of c.e sets. If $I$ is c.e, then for all $x$, $x \in I$ if and only if there is $y \in I$ such that $W_y$ is a finite subset of $W_x$.

  Or equivalently

  $I$ is c.e $\Rightarrow$

  $~~~~(1):~ \forall x,y ~ (x \in I \land W_x \subseteq W_y \rightarrow y \in I)$

  $\land ~~(2):~ \forall x ~ (x \in I \rightarrow \exists y~(y \in I \land W_y ~\text{is finite} \land W_y \subseteq W_x))$

My question is if it's converse is also true, that is, if (1) and (2) hold, then $I$ is c.e.

So I found another (weaker) formulation of the theorem in H. Rogers Theory of Recursive Functions and Effective Computability p. 324, which states:

  version B

  $I$ is c.e $\iff ~(3):~ \forall x ( x \in I \leftrightarrow \exists u (D_{f(u)} \subseteq W_x))$ for some totally computable function $f$

where $D$ is the canonical enumeration of the finite sets (see definition 2.4).

(3) implies that $I$ is c.e, for it is just a $\Sigma_1$ representation of $I$.
On the other hand, if $I$ is c.e, by s-m-n theorem take the totally computable function $g$ to be defined such that $W_{g(x)} = D_x$. Now the set $g^{-1}(I) = \{ x : \exists y (g(x) = y \land y \in I)\}$ is also c.e, thus there must be a totally computable function $f$ such that $Range(f) = g^{-1}(I)$. So by version A of the theorem, we also have (1) and (2), which imply that this $f$ is the function that satisfies (3).

I also found these two answers which state the theorem in bidirectional form, but with an additional condition:

  version C

  $I$ is c.e $\iff (1) \land (2)$

  $~~~~~~~~~~~~~~~~\land (4):~ \{ e : D_e \in \Gamma \}$ is c.e

Now this set in (4) is just the $g^{-1}(I)$ defined above, where we just saw that it is indeed c.e. by the sole fact that $I$ is c.e. So my primitive guess is that (4) is the ingredient for proving the other direction.

Considering all the observations above, my question is whether the right to left direction holds generally, i.e. does (1) and (2) imply $I$ is c.e? And is there a counterexample if that fails? Assuming (4), can we deduce that $I$ is c.e? And does that mean the wanted counterexample should refute (4)?


texts: Why are greedy algorithms used to find upper/lower bounds? (when they doesn't guarantee an optimal solution)

texts:
Take the nearest neighbor algorithm for the traveling salesman problem as an example. Why is it used to find the upper bound? When can't it guarantee an optimal solution?

(Thanks to many comments below, which suggest (and are invalidated by) the last update of this question)


texts: Significance of including $S \to ε$ production rule in regular grammar?

texts: Why a production rule $S\to ε$ has been included in the definition of regular grammar? In that case, why it is restricted for $S$ (start symbol) to be present on right hand side of any production rule?


texts: Prove that a 3D packing problem is NP-complete

texts:
How can I prove that the following problem is NP-complete?
I have a spherical container in which I have to introduce $n$ identical spheres. All of the little spheres have to be inside the container and they can't overlap each other. The idea is to minimize the container's ratio.
I know that this is a packing problem but it is three-dimensional so I don't know how to prove that it's an NP-complete problem. Can you help me?
The problem appears in Hifi and Yousef, A hybrid algorithm for packing identical spheres into a container. From the introduction:

In this paper, the Identical Sphere Packing (denoted ISP) is tackled with a hybrid algorithm that combines the particle swarm optimization and an efficient continuous local optimization. Two types of ISP are considered: the ISP with an Open container (denoted O-ISP), where the container has an unlimited length, and the ISP with a spherical container (denoted S-ISP), where its radius is unlimited.
An instance of each of both problems is characterized by a set $N$ of $n$ identical spheres, where each sphere $i \in N = \{1, \ldots, n\}$ is represented by its radius $r_i=1$ and the container is either $\mathscr{P}$ with fixed width $W$ and height $H$ but unlimited length $L_0 = \infty$ or $\mathscr{S}$ of unlimited radius $S = \infty$. For both versions of the problem, the goal is to minimize the length $L_0$ (if the container $\mathscr{P}$ is open) or the radius $R_0$ (if the container $\mathscr{S}$ is spherical) such that all items of $N$ are positioned in $\mathscr{P}$ or $R_0$, without overlapping between spheres and between spheres and the container.

I am interested in the second problem, S-ISP.


texts: Can context-free grammar generate $a^{2^n}$?

texts:
Context-free grammar can generate the string a 2 n    for n≥0 .

The production rule P is S→SS|a .

The derivations is, for example:

1) S⇒a  (this is when n = 0)

2) S⇒SS⇒aa  (this is when n = 1)

3) S⇒SS⇒SSSS⇒aaaa  (this is when n = 2)

4) S⇒SS⇒SSSS⇒SSSSSSSS⇒aaaaaaaa  (this is when n = 3).

Am I right?

Someone told me yes but it takes a very long time for big enough n;

someone told me no - that this grammar actually generates $a^+$ because it can be $S \Rightarrow SS \Rightarrow SSS \Rightarrow aaa$.

So, does this mean context-free grammar cannot generate the string $a^{2^n}$?

Is there exist any other context-free grammars that can generate this language?


texts: How to perform particle swarm optimization clustering of results obtained from tf-idf vectorizer?

texts:
I have a collection of news articles. I have performed tf-idf operations on them. I am using python as programming language so it was just the use of TF-IDF vectorizer function. I now have the document's tfidf representation. My aim is to cluster news articles using Particle swarm optimization.

As read in following research papers,

https://www.researchgate.net/publication/4170865_Document_clustering_using_particle_swarm_optimization
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0188815
https://www.sciencedirect.com/science/article/pii/S1877750316305002

the input of the PSO algorithm should be an array representing document. In my case I am trying to use tf-idf as input. So, how can i use the result of tf-idf as input for Particle Swarm optimization? Particle Swarm optimization is a optimization algorithm. So while clustering, I am going to optimize or minimize distance between cluster's centroid and data points belonging to that cluster. Can anybody provide me a solution or hint towards something?


texts: Is there a greedy algorithm to solve the assignment problem?

texts:
The assignment problem is defined as:

There are n people who need to be assigned to n jobs, one person per job. The cost that would accrue if the ith person is assigned to the jth job is a known quantity C[i,j] for each pair i, j = 1, 2, ..., n. The problem is to find an assignment with the minimum total cost.

There is a question asking to design a greedy algorithm to solve the problem. It also asks if the greedy algorithm always yields an optimal solution and for the performance class of the algorithm. Here is my attempt at designing an algorithm:

Am I correct in saying that my algorithm is of O(n^2)? Am I also correct in saying that a greedy algorithm does not always yield an optimal solution? I used my algorithm on the following cost matrix and it is clearly not the optimal solution. Did I Do something wrong?


texts: Converting a special case TM to a regular TM

texts:
So, I have been given a TM where the head can access and write both the character that the head is pointing at and the next character to the right.
So if we have a TM abbb and the head is pointing at a, it can access and write into the the next character also ie the first b. So it has access to both the first and second characters of the string abbb. How would I show that this isn't actually a special TM but can be done with a regular TM too?


texts: Is the reverse postorder of a digraph's reverse the same as the postorder of the digraph?

texts:
I've been reading Sedgewick's intro to algorithms book, and he says that the reverse postorder of a digraph's reverse is not the same as the postorder of the digraph, however in both cases it seems that we get the reverse of topological order, so at first I thought that it's the same, but then I looked on his website and he answers "False".

If you think about it, in postorder of a digraph, we first visit every child of the vertex and add it to some queue, hence since the children are visited first, we get the order which is the reverse of topological.

Why does Sedgewick say they're not the same?


texts:
There is a land divided to $D$ districts.

There are $C$ citizens.

We want to divide the land to the citizens, such that each citizen receives a single land-plot in a single district.

Each citizen prefers certain districts, however, the preference also depends on the size of plot. For example, Johnny prefers a plot of 1 dunam in the North to a plot of the 1 dunam in the South, however, he also prefers a plot of 1 dunam in the South to a plot of 0.5 dunams in the North.

Ideally, we would like to divide the land in an envy-free manner, such that no citizen thinks that the plot given to another citizen is better (according to his subjective preferences) than the plot given to him.

However, this is not always possible. For example, suppose there are 2 districts (North and South), each of size 1 dunam, and 3 citizens, all have the same preferences as Johnny. If two of them get a plot in the North and the third gets a plot in the South, then the first two get only 0.5 dunam each, and so they envy the third who gets 1 dunam. The other divisions are even worse (In the singular case where all citizens get 1/3 dunam in the North and the South remains empty, assume that it is invaded by a fourth citizen, so that all 3 citizens now envy the invader).

So, I am looking for a procedure that will minimize the envy - whatever that means.

Note that, in contrast to the standard envy-free cake-division algorithms, I am not interested in geometric cuts of the land - the division of land to districts is pre-determined, and each person can get a plot in only one district.


texts: Create a Turing-machine that decides $A=\{0^{3^n} | n\ge 0\}$

texts:
I need to find a Turing machine that decides $A=\{0^{3^n} | n\ge 0\}$.
I tried doing the same as Sipser does on page 172 in his back, where he creates a Turing machines that decides $A=\{0^{2^n} | n\ge 0\}$, by iterating over the input, and crossing (by writing $x$) on every other $0$.
I wanted to cross every third $0$, but I failed getting to any possible machine. Either I create a machine that does not accept $000$, or a machine that accepts $00000$ or $000000$.
I found a solution that for each iteration cross off $2/3$ of the $0$ over the tape, meaning after each iteration we remain with third of the $0$. But is it possible to get to a solution as I wanted? where on each iteration we cross off third, and remain with $2/3$?


texts: Implicit Leading 1 in Binary Floating Point

texts: Is the convention of dropping the leading 1 when storing the significand a given in all binary floating point representations or not necessarily?


texts:
Many areas in the world suffer from conflicts between two groups (usually ethnic or religious). For the purpose of this question, I assume that most people of both sides want to live in peace, but there are few extremists who incite hatred and violence. The goal of this question is to find an objective way to filter out those extremists.

Imagine a town with 2 conflicting groups, A and B, each has N people. I propose the following voting scheme (which I explain from the point of view of group A, but it's entirely symmetric for the other group):

equality-rule: The number of people in each group must always remain equal.
expel-vote: At any time, each person of group A can claim that a certain person of group B is "extremist", and start a vote. If more than 50% of the people in group A agree, then that certain person is expelled from town.
counter-vote: To keep the equality-rule, a single person of group A should also leave the town. This person is selected by a vote between the people in group B (i.e. each person in group B votes for a single person in group A, and the one with most votes is expelled from town).

My intuition is that:

On one hand, this scheme encourages people to be nice to people of the other group, so that they won't be subject to expel-votes.
On the other hand, the equality rule encourages people to think twice before starting an expel-vote, because this will put them in danger of expel in the counter-vote.

[ADDITION]
Several questions can be asked about this scheme, for example:

Under what conditions does it diverge to a situation where people vote and counter-vote, until the number of citizens in one of the groups reaches 0?
Under what conditions does it stabilize on a situation where the two group has more than 0 citizens?
Under what conditions, the stable number of citizens is more than half the initial number?

Note that this scheme does not even try to reach an objective measure of "extremism". The only goal is stability.

I would like to know, has this voting scheme has been studied in the past?


texts:
I am confused regarding the absorption rule which states: A OR (A AND B) = A.

I do not completely understand how the expression simplifies to A and while i have seen proofs for this question, i still feel that i don't completely grasp it.

I will outline my working out below:

if expression = A OR (A AND B) then, according to the commutative rule we can rewrite this as (A OR A) AND B. (A OR A) simplifies to A. This means we should be left with A AND B. However, the expression simplifies to A which i don't understand.
Why is this the case?


texts: Find maximal difference between two consecutive numbers

texts:
You are given $n$ real (unsorted) numbers $_1,_2,...,x_n$. We want to compute the maximal difference between two consecutive numbers in sorted order. Explain how to do it in $()$ time when you are allowed to use additions, subtractions, multiplications, divisions and “floor” function. Notice that sorting immediately leads to $( log)$ time.
Please help !


texts: Node depth in randomly built binary search tree

texts:
It can be proved that randomly built binary search trees of size $n$ are of depth $O(\log n)$ and it is clear that level $k$ has at most $2^{k}$ nodes (root's level is 0).

I have an algorithm that traverses every path in the tree (beginning at the root) but stops after traversing $k$ nodes (the parameter $k$ is a configurable parameter which is independent of the size of the tree $n$).

For any tree $T$ with $\mathit{depth}(T) > k$, the algorithm will miss some nodes of the tree. I would like to bound the probability of my algorithm missing a large number of nodes.

Formalizing it: let $T$ be a randomly built binary search tree of $n$ nodes.  I would like to calculate the probability for a node to have depth larger than $k$, as a function of $n$ and $k$.


texts: How do I visit all edges incident to a vertex in a DCEL data structure?

texts:
In a doubly-connected edge list (DCEL) data structure, each vertex v stores a pointer to one arbitrary half-edge, v.inc, which has v as its origin, that is, v.inc.origin == v. However, there may be multiple half-edges which have v as its origin.

How do I access or iterate all half-edges which have v has their origin?


texts: Turing machine with possible transitions to the final state

texts:
Let's say we want to draw the transition graph of a Turing Machine that accepts that language L and then write the sequence of moves done by the TM when the input sequence is $w = abbcbba$ so I had some thoughts on how this could be built.

$q0 - q1: a,a,R$

$q1-q2: b,b,R$

$q2 (loop): b,b,R$

$q2-q3: c,c,R$

$q3-q4: b,b,R$

But then I'm getting stuck here, I could see $b,b,R$ to the final state and then add a separate node to account for the case $m=3$, but I'm teaching this to myself so maybe someone can step in here and get me back on track.

EDIT:

This might work:


texts: Why can we not find the generally superior machine learning algorithm in practice?

texts:
TL;DR Our mind is a superior meta-machine learning algorithm, it can figure out tradeoffs in a much more general case than any machine learning algorithm we have. Furthermore, its Kolmogorov complexity is 4MB or less, and thus should be fairly easy to discover. However, despite our best efforts, no algorithm we've discovered has even approached this meta-capability. Is there a CS grounded explanation for this?  The NFLT is not applicable because it does not apply in practice, and the human mind is an instance of said meta-algorithm.

There are many machine learning algorithms.  The no free lunch theorem (NFLT) says, in theory, all these algorithms are exactly equal according to an error function over all possible problem domains.  In practice, this doesn't matter because we are only dealing with a very small subset of these problem domains.

In practice, this often involves a tradeoff between multiple objectives.  Making a problem multi-objective instead of single objective often causes it to become much more complex and difficult.  There is no longer a single best solution, but there are still better and worse solutions.  One way of describing the set of better solutions is with the notion of "Pareto optimality," which is the set of solutions that dominate all other solutions in all objectives, but do not dominate each other.  These optimal solutions describe a surface in a graph of the solutions known as the "Pareto front."  The following Figure is an example of a Pareto front where solutions A-H dominate all other solutions, but not each other.

That being the case, if we ask "what is the best ML algorithm?" we cannot say "None, b/c NFLT," since we are asking about the best ML algorithm in practice.  If the NFLT does not matter in practice, then there must be a best ML algorithm, in practice.  If there is a set of algorithms that describe the Pareto front, then the best algorithm is any member of this set.

What is this best practical algorithm?  There does not seem to be one, to the best of our knowledge.  Even "magical" general ML algorithms such as deep learning or extreme boosting have many knobs to twiddle, and are only good for the right kind of problem.  There is no one size fits all ML paradigm.

Yet, there must be one, since data scientists are able to match the right algorithm to the right problem and achieve outstanding results, such as Google's search capabilities.  Whatever it is that powers the data scientist brain must be relatively simple, since human DNA can be compressed to 4 MB, not much bigger than, and often quite smaller than, many ML frameworks when zipped.

Furthermore, the data scientist brain algorithm is an extremely powerful program.  For a binary prediction problem of $N$ predictions, there are $2^N$ different possible predictions.  To be right more than half the time, we need to eliminate more than $2^{N-1}$ possibilities.  We also have to do this in polynomial time.  Both feats seem astounding for any reasonably sized $N$, especially since so many important problems are NP-Complete or worse in the general case.

Since we aren't dealing with a halting problem (data scientists reliably halt on good solutions), even some kind of assisted enumeration of 4MB programs in a Turing complete language would seem to hit on this master algorithm sooner or later.

Is there a CS explanation for this discrepancy, or flaw in my reasoning, that the super powerful and extremely quick master algorithm is <= 4MB, yet despite all our searching we've been unable to find it?


texts: Does the following transformation preserve context-freeness?

texts:
I encountered this problem involving manipulating a context-free language. Let $L$ be a context-free language. Define $L^{\#} = \{ x : x^i \in L$ for every $i=0,1,2,...\}$. Is $L^{\#}$ always context-free?
My guess is that it will preserve context-freeness. Can anyone provide an elementary proof of this?


texts: Why vertices of directed acyclic graph are considered strongly-connected components?

texts: Well the title pretty much says it all, I've heard our professor saying that the smallest strongly-connected components in DAG (directed acyclic graph) are its vertices. Sadly I was unable to ask him for explanation and now this is stuck in my head ever since.


texts: Randomly select a uniform subsample from a nonuniform dataset

texts:
I have a dataset of events with timestamps spanning several months. The event rate is "bursty", i.e. there are periods of much higher and lower rate than the average.  I would like to randomly select a subset of these events having approximately uniform time distribution. What weight should be applied to the random sampling?

One approach I've already considered is to histogram the data and weight samples by 1/binheight, but this ends up being dependent on the binning chosen and runs into problems with very sparse samples.

Can the appropriate method also be extended to another, possibly related parameter?  For example, I may have a unix timestamp (1 second resolution) and another parameter measuring phase of the 60 Hz AC power line. My subsample should be uniform in both dimensions.


texts: DFA, lower bound on number of states, language with primes and remainders

texts:
This is an exercise from old exam on formal languages that I don't know how to solve:

Let $p \ge 5$ be a prime number and $L_p$ be a language of words over $\{0,1\}$ that read in binary from right (i.e. from least significant bit) give a number that gives remainder modulo $p$ from the set $\{1,2, \ldots, \frac{p-1}{2}\}$.

How to show that:

  Every DFA recognizing $L_p$ has at least $2p$ states.

?

One fact that I know of and is somehow related (has DFA and primes in the statement) is:

  Any DFA recognizing language $\{0^n : n \text{ is not divisible by } p\}$ has at least $p$ states.

This can be seen by observing that the language is infinite, hence any DFA must have a reachable cycle, from which some accepting state is reachable. And if that cycle had less than $p$ states, then because any number smaller than $p$ is coprime with $p$, we could loop sufficiently many times in that cycle and arrive at the aforementioned accepted state with a word $0^{kp}$ for some natural $k$ - a contradiction.

Maybe it's possible to use this fact, or alter this proof somehow to make it fit for the theorem with $L_p$?

--EDIT

I'm trying to solve it by Myhill-Nerode theorem, as Yuval Filmus suggested.
So, the goal is to find $2p$ words $w_1, \ldots, w_{2p}$ that will be pairwise distinguishable. I don't have a good intuition here but let's define $w_i$ to be $rev(bin(i))$ for $i = 1, \ldots, 2p$ ($bin(a)$ gives a binary representation of number $a$, and $rev(w)$ reverses the word $w$). Let's take any $i \neq j$ that both belong to $L_p$, or both don't. Now the task becomes a bit number-theoretic -- adding a common suffix $x$ to these words changes their values such that $val(w_ix) = val(w_i) + 2^{length(w_i)-1}val(x)$ (and similarly for $j$), where $val(\cdot)$ gives value of binary string reading from LSB (so e.g. $val(01) = 2$).
Now the question is: can we always find an appropriate $x$ that makes one of $w_ix, w_jx$ belong to $L_p$, and the other not? I don't know the answer to this question. Maybe I should use the fact, that $2$ is a multiplicative generator modulo $p$?


texts:
Given a string, is it possible to determine which hashing algorithm has produced it, if any?

For example, the MD5 hash of "string" is b45cffe084dd3d20d928bee85e7b0f21.

Is it possible to determine whether the above hash is:

1) Indeed a genuine hash in some hashing algorithm, as opposed to a string of characters that is not a hash produced by one of some set of algorithms

2) a definite hash of a specific hashing algorithm?

Possible methods:

1) For hashes susceptible to rainbow-table attacks, it would be viable to search for the hash in such a rainbow table for various algorithms, to find a match; if a match is found, we know which algorithm produced it.


texts:
Suppose we have the following grammar:

S -> A ( S ) B | ε
A -> S | S B | x | ε
B -> S B | y

where S is the start symbol, S, A, B are non-terminal symbols, x, y, (, ) are terminal symbols, and ε is the empty string.

I'm trying to compute the FIRST() and FOLLOW() sets of S, A, and B.

FIRST(S) = FIRST(A ( S ) B) ∪ {ε}
FIRST(A) = FIRST(S) ∪ FIRST(SB) ∪ {x} ∪ {ε}
FIRST(B) = FIRST(S B) ∪ {y}

How can I compute FIRST(S), since I don't know what the FIRST(A) is? How should I attack the problem? Any ideas?


texts: I have a connected undirected graph with V vertices and V(V - 1)/2 edges. Then, I remove K edges (a[i], b[i]). I want to know if the graph is still connected after performing all the operations (so I want to delete those edges and then answer the question). Is there any faster way to do this than performing BFS/DFS algorithm? Those are linear time algorithms but in terms of edges which may be quite big to compute on a home PC for graphs with approximately 10^6 vertices. K of course will not be too big, let's say 10^6.


texts:
What does it mean that the bound $2n^2 = O(n^2)$ is asymptotically tight while $2n = O(n^2)$ is not? We use the o-notation to denote an upper bound that is not asymptotically tight.

The deﬁnitions of O-notation and o-notation are similar. The main difference is that in $f(n) = O(g(n))$, the bound $0 \leq f(n) \leq cg(n)$ holds for some constant, $c>0$, but in $f(n) = o(g(n))$, the bound $0 \leq f(n) < cg(n)$ holds for all constants, $c>0$.
So what is the difference in big-O notation and small-o notation?


texts: which algorithm GNU make uses to travel the dependency graph?

texts:
Make is a very common English word and consequently I cannot find the answer using google.
I am writing a script to automate all the data generation process, which resembles what GNU make does.
I am curious to know which type of algorithm GNU make uses under the hood. I suppose it is some sort topological sort with BFS/DFS. Can anyone provide any insight or provide a reference ? thanks


texts:
I have a problem P that is said to be O(n^7) in the worst case.
I'm asked to agree or not if it is solvable in O(n^9) time. And also I'm asked to agree or not if P cannot be solved faster than Ω(n^7) in the worst case.

My answer for the first question is that if P is bounded by O(n^7) it is also solvable in O(n^9).

And for the second question: Ω(n^7) means that the running time cannot be less than n^7, but we already know that P is bounded by O(n^7) in the worst case and it is not proven that it can't be solved faster, so I think this statement is false.

So my questions are: how do I prove the answer for the first question and how do I express my second answer in terms of functions?
I've seen a lot of info about asymptotic notations, but I couldn't find any info that could enlighten me how to answer the questions I am asked.

Thanks.


texts: Is a stack machine with a forward read iterator Turing complete?

texts:
It is well known that a machine with a single stack as only unlimited storage is not Turing complete, if it can only read from the top of the stack. I want a machine which is (slightly) more powerful than a stack machine, but still not Turing complete. (I wonder whether there exists a non-Turing complete machine, which can deterministically simulate any non-deterministic pushdown automata with an only polynomial slow-down.) The most benign (straightforward) extension that came to my mind was a (single) forward read iterator.

Let me elaborate the implementation details, to make it clear what I mean by a forward read iterator. A singly linked list can be used for implementing a stack. Let the list be implemented by a pointer pTop, which is either zero, or points to an SList node. An SList node consists of a payload field value and a pointer field pNext, where pNext is either zero, or points to an SList node. Let the forward read iterator be implemented by a pointer pRead, which is either zero, or points to an SListnode. The pointers pTop and pRead cannot be accessed directly, but can only be used via the following methods:

Push(val) creates a new SList node n with n.value = val and n.pNext = pTop, and sets pTop = &n.
Pop() aborts if pTop == 0 or pRead == pTop. Otherwise it reads val = pTop->value and pTopNext = pTop->pNext, frees the SList node pointed to by pTop, sets pTop = pTopNext and returns val.
ReadBegin() sets pRead = pTop.
ReadNext() aborts if pRead == 0. Otherwise it reads val = pRead->value, sets pRead = pRead->pNext and returns val.
ReadFinished() returns true if pRead == 0, and false otherwise.


texts: Non-quadratic search for specific difference between elements in sorted array

texts:
New to computer science and am attempting to verify if there are any non-quadratic approaches (i.e. better performance than Big-O of n^2) for finding a potential specific difference between either adjacent or nonadjacent elements in a sorted array of integers?

For example, if you have an array that's already been sorted, like so:

[1, 4, 6, 6, 10, 12, 13, 15, 16]

And you want to find if there's a difference between any of these elements that equals 3, the pairs here would be 4, 1 and 15, 12 and 13, 10.

But is there an algorithmic approach that would allow me to find these pairs without using two for loops?


texts: What's the difference between Computer Science and Informatics?

texts: The Terms are much used in actual IT (Information Technology). Is it possible to make a difference or are this terms nearly synonyms for the same fact?


texts: prove correctness of in-order tree traversal subroutine

texts:
I'm trying to prove that in-order tree traversal prints the keys in sorted order. it's shown here, but what I want is to prove correctness using ordinary induction.

Claim: For any n-node  subtree, the in-order-tree-walk subroutine prints the keys of the subtree rooted at node x in sorted order.

in-order-tree-walk(x)
  if(x!=NIL)
    in-order-tree-walk(x.left)
    print x.key
    in-order-tree-walk(x.right)

Above pseudo-code is taken from CLRS, and we're traversing the subtree rooted at node x.

Proof. By ordinary induction. Let our induction hypothesis $P(n)$ be the claim itself. We need show $P(n)$ holds for all positive integers.
Base case ($n=1$): in-order-tree-walk subroutine prints the single node's key and, since the both left and right pointers are NIL, terminates. Trivially, single key is already in sorted order.
Inductive step: Suppose $P(n)$ holds for some $n \geq 1$. Prove $P(n+1)$. Let $T$ be subtree consisting of $n+1$ nodes. Let $T'$ be subtree formed by removing the largest element from $T$. $T'$ has $n$ elements. By induction hypothesis $P(n)$, in-order-tree-walk(T') prints keys of subtree rooted at T'.root in sorted order. By binary-search-tree property, largest element in the tree is placed on the rightmost node and it's the last node visited during the in-order-tree traversal. So, that rightmost node's key is printed after the keys of $T'$ is printed. Since it's the largest element in $T$, and keys of $T'$ in printed in sorted order, we can conclude that in-order-tree-walk(T') prints keys of $T$ in sorted order.
By induction principle, we can conclude that $P(n)$ holds for all positive integers.

Can we show correctness using this induction proof? Is any parts of the proof need to be revised? I appreciate your efforts.
EDIT: trees/subtrees in this post refer to binary search trees. Binary search tree property is preassumed


texts: Extracting non-duplicate cells in a particular matrix with repeated entries

texts:
Consider a board of $n$ x $n$ cells, where $n = 2k, k≥2$. Each of the numbers from $S = \left\{1,...,\frac{n^2}{2}\right\}$ is written to two cells so that each cell contains exactly one number.

How can I show that $n$ cells $c_{i, j}$ can be chosen with one cell per row and one cell per column such that no pair of cells contains the same number.

This was an example problem for an exam I'm studying for. I tried it now for several hours but I can't get it right. I think random permutations can help here but I am not sure.


texts: Interval partitioning problem different approach - arrange lectures in minimum number of classrooms

texts:
The problem of scheduling lectures in minimum number of classrooms is as follows:
Find minimum number of classrooms to schedule all lecture so that no two occur at the same time in the same room.

The common algorithm that I find in books is:

Sort intervals by starting time so that s1 ≤ s2 ≤ ... ≤ sn.
d ← 0 //number of classrooms
for j = 1 to n {
 if (lecture j is compatible with some classroom k)
 schedule lecture j in classroom k
 else
 allocate a new classroom d + 1
 schedule lecture j in classroom d + 1
 d ← d + 1
}

Now, I was thinking of an alternate approach where I sort my lectures by finishing times in ascending order and every time I check if lecture j is compatible with some classroom k and there are multiple classrooms that are compatible with that lecture, I schedule it in the classroom which the last jobs finish time in that classroom is closest to that jobs start time, i.e minimise the time a classroom is empty.

Sort intervals by starting time so that f1 ≤ f2 ≤ ... ≤ fn.
d ← 0 //number of classrooms
for j = 1 to n {
 if (lecture j is compatible with some classroom k)
 schedule lecture j in classroom k which was used last
 else
 allocate a new classroom d + 1
 schedule lecture j in classroom d + 1
 d ← d + 1
}

I would like to know if this approach is right(not necessarily optimal). I have dry run it on a couple of cases, and looks to be okay. If yes, how can I prove its correctness? If not, how can what changes can I make the algorithm work.


texts: What undecidable language $B$ is reducible to its complement?

texts:
I encountered a problem which asks to give an example of an undecidable language $B$ such that $B \leq_m \overline{B}$...
However, I could find it hard to construct an example ... my difficulty is that given an undecidable but Turing recognizable language, say $A_{TM}$, its complement $\overline{A_{TM}}$ is not Turing recognizable and loops. If I reduce such a language (say $x \in A_{TM} \leq_m y \in  \overline{A_{TM}}$, the instance $y \in \overline{A_{TM}}$ cannot be recognized by any TM (since by definition, $\overline{A_{TM}}$ is looping)...
Any help ?


texts:
I am pretty desperate finding the correct context free grammar for the following language:
$$L=\{a^lb^mc^n \mid l,m,n \in \mathbb{N}_0, \, l\geq 2n+m\}$$

I would really appreciate if anyone could tell me how to generate the CFG from this language as I am stuck on this one for 2 days now.

I can't find a solution for adding the right amount of $b$'s and $c$'s to a generated string.

At the moment I have:
$$ \begin{align*}
S &\rightarrow aS \mid T \mid U \mid \varepsilon \\
T &\rightarrow aTb \mid \varepsilon \\
U &\rightarrow aaUc \mid \varepsilon
\end{align*}$$


texts: What is the difference between E-Science Infrastructures and Distributed Computing Infrastructures?

texts:
What is the difference between eScience infrastructures and grid computing or distributed computing infrastructures? And what are some of their examples.

I can not distinguish them clearly. Is it how a grid is used make it an e-science platform?


texts: Finding CNF of $(p \rightarrow q) \rightarrow p$ and $\lnot (q \wedge (\lnot p \rightarrow q)) $

texts:
I'm trying to find the CNF of the $(p \rightarrow q) \rightarrow p$ and $\lnot (q \wedge (\lnot p \rightarrow q))$, and afterwards proving it's validity. As i'm new to CNF i wanted to ensure i've found the right CNF before trying to move on, so for $(p \rightarrow q) \rightarrow p$:

the normal from is:
$p \rightarrow q \wedge q \rightarrow p$

and it's valid?


texts: Who invented the state elimination algorithm for converting finite automata into regular expressions?

texts:
The state elimination algorithm is an algorithm for converting finite automata into regular expressions. It's found in many textbooks, including Sipser's Introduction to the Theory of Computation. However, I can't seem to find any references to who first invented this algorithm.

Does anyone know who invented the state elimination algorithm? Ideally, I'd like a reference to a specific paper or textbook.

Thanks!


texts: Flaw in linear programming solution for multi-commodity flow problem?

texts:
The multi-commodity flow problem problem statement - wiki

According to constraints of multi-commodity flow problem a given material must start at source s with demand d and end up at its target t. The linear program form of this problem as given in clrs is

f is flow, c is capacity, u and v are vertices, d is demand, s is source, t is target(sink). We are given k commodities. i corresponds to ith commodity.

Now How does these constraints guarantee that i commodity will end up only in target of i (ti) with its respective demand (di)

Why It works for single commodity case

In single commodity case it includes all the constraints. This is popularly known as the Maximum Flow problem. The first constraint is capacity constraint, the second one is flow conservation. The fourth implies flow is non-negative.

Why There is Problem for the multi-commodity case ?

There is no constraint on target which guarantees that flow will only go into its respective case.

For instance, this seems like a simple counter example:


texts: Boolean algebra truths with more than one digit

texts: I understand that when you 0 AND 0 it will result in 0 and that 1 AND 1 will result in 1 etc but what I don't understand is if the question was 01 AND 11. How would I work this out?


texts: How can I show that a problem is not $NP$

texts:
Consider the following image:

The problem is: can we cover the bigger rectangle with small rectangles such that no two rectangles overlap and no gap opens up? Prove that this problem is $NP-Hard$.

I know that to prove that it is $NP-hard$, I must reduce a $NPC$ problem to it.

However, I guess that the problem is not $NP$, right? For example, even if we have a "Yes" answer for the items above, how can we fit the small rectangles into the big rectangle in polynomial time?

For the above problem, the answer can includes the placement of small rectangles in the bigger rectangle. So, verifying it is easy, and the problem is $NP$.

Suppose, the question was: is there any subset of rectangles that cover the bigger rectangle so no two rectangles overlap and no gap opens up?

Then, what would be the shape of a certificate? Would it be verifiable in polynomial time? Would it be just a subset of items, or their placements too?

What if it was an optimization problem requesting a subset of items that cover the largest area of the bigger rectangle? Then, we had to check other answers to see that the certificate is the optimum one, and that would make the problem non-NP, right?

How a certificate is defined in such cases, and what is its role in categorizing a problem as $NP$ or non-$NP$?!


texts: Generating path vectors from point-to-point data

texts:
I have a list of point-to-point $(x,y)$ positions representing a path. I would like to convert these points to a list of vectors consisting of straight segments $\{L\}$ and turn vectors $\{r, \theta\}$, where turns are represented by arcs on a circle. For example, the set of points

(0,0), (0,10), (5,15), (10,10), (10,0)

would be converted to

(10), (5,180°), (10)

Note that the start point and heading angle of a new vector is the end point/heading of the previous vector. The only way I can change the direction of the path is by conducting a circular turn. The original point data is generated using similar rules.

What is the best way of doing this?

This is how I'm currently approaching the problem:

$P_0$ to $P_1$ is assumed to be a straight vector (not necessarily correct). This gives us a heading angle $\phi_{0}$.
If the heading angle from $P_1$ to $P_2$ is different from the heading angle from $P_0$ to $P_1$ (i.e. $\phi_0 \ne \phi_1$), initiate a turn segment.

The position of $P_1$ is saved. $P_1$ is the endpoint of the first straight vector, and the startpoint of the turn vector.
$P_2$ is the next point in the turn vector

By necessity, $P_3$ must also be in the turn vector (it takes 3 points to identify a distinct circle).

From these three points, we can identify a distinct circumcenter and circumradius, $\{x,y,r\}_0$, of the circle representing this turn.

For each new point after, we determine whether it is part of the same turn by calculating the new point's error. This is where it gets problematic:

There may be some "fuzziness" in the positions of the points. This makes the original $\{x,y,r\}_0$ potentially inaccurate, because locally the first 3 points may curve one way but the overall trend of the turn is to inflect the other way:

To overcome this, I use the Modified Least Squares method introduced by Umbach and Jones to determine a new circumcenter and circumradius from the original 3 points and the next new point, $P_1, P_2, P_3, P_4$.
I continue to calculate new circumcenters and circumradii for each new point. If they are all part of the same turn, they will tend towards a single circumcenter and circumradius, $\{x,y,r\}_1$.
At the same time, I track the distance from a new point to the current circumcenter. If the distance from a new point, $P_n$ to the circumcenter exceeds the circumradius by more than, say, 5%, then the turn has ended ($P_{n-1}$ is the last point in the turn).

The circumradius becomes the radius $r$ used to define the turn vector. The turn angle $\theta$ is simply the angle between the first point in the turn, $P_1$, the circumcenter, and the last point in the turn, $P_{n-1}$.
Determine whether the vector from $P_{n-1}$ to $P_n$ is straight or a turn by going to Step 2. Repeat until all points have been examined.

Unfortunately this does not seem to work for all cases, and my results don't seem to sufficiently match my original data. It also seems needlessly complex. I'm wondering if there's a better, non-bruteforce, less naive way of approaching this problem.


texts: Algorithm to calculate the period where cumulative days within a rolling period exceeds a threshold

texts:
I'm struggling to think of the algorithm to transform one data set to another.
The problem I'm looking at is creating a dataset of periods of time where cumulative days absent within a period (eg 30 days) is greater than a certain threshold (eg 14 days). I can easily determine what sub-periods are within master-period the The dataset I'm working from is

Absence_ID
Absence_Start
Absence_End

1
10/01/2021
16/01/2021

2
23/01/2021
30/01/2021

So in this example the rolling 30 day period would result in the cumulative sum of days exceeding 14 on the 29th of January and ending on the 11th of February

Exception_ID
Exception_Start
Exception_End

1
29/01/2021
11/02/2021

But because the sub-periods vary in duration, start and number (n > 0) I'm struggling to get an initial insight into calculating Exception_Start and Exception_End.
Brute force checking each day isn't ideal due to the scale of the data.


texts: Optimizing electoral votes in a political simulation... 200,000+ possibilities, how to run through them?

texts:
So basically, in my government class, we are simulating a presidential election. Our grade comes from the presentation of our candidate, but as an added challenge our teacher has a running count of electoral votes garnered. How it works is like this:

there are only 18 states amounting to 286 delegates, so 144 needed to win
Candidates get a +1 'influence' in certain states (for example home state or somewhere they're popular) and -1, as do VP candidates.
Some states (CA and TX) have a pre-existing leaning of up to 2 'influences'.
You need to choose 4 issues you're against and 4 you're for, out of a list of 14. Each state has an issue they're against or for. As expected, being in agreement with a state nets you +1 in that state and disagreement nets you -1.
If you have more influence in the state, you win it. If it's tied at 0, then the popular vote (the class) gets to decide)

I'm trying to lock up the nomination without even needing to get the popular votes, and I'm trying to figure out what software I could use to do this. I know excel and python 3 at a basic level, but I'm wondering if there's some other way to do it.

Here is an image of what I'm talking about (as you can see, I'm playing as the republicans here). Also, the for and against positions formulas link to here. Now, if I need to choose 4 issues to be for and against, I think that's 14 choose 4 times 10 choose 4, which gives me 210,210 possible combinations. Is there a way to run through all of these to see which will give me the highest Net Electoral Vote count with the lowest closeness factor? Obviously, I don't know my opponents topics yet, but I'd like to have the largest margin of error possible to prevent them from flipping states.

Thanks for any help. tips, advice or comments!

TL;DR: Political simulation, have to find best possible combination of issues to talk about out of 200,000+ possibilities, how do I run through them?


texts: How to modify semantic actions when removing left-recursion from a grammer

texts:
Is there any algorithm that tells us how to modify semantic actions associated with a left-recursive grammar? For example, we have the following grammar, and its associated semantic actions:

$ S \rightarrow id = expr $  { S.s = expr.size }

S $\rightarrow$ if expr then $S_1$ else $S_2$ { $S_1.t = S.t + 2; $
$S_2.t = S.t + 2;$ $S.s = expr.size + S_1.size + S_2.size + 2;$ }

S $\rightarrow$ while expr do $S_1$ { $S_1.t = S.t + 4;$ $S.s = expr.size + S_1.s + 1;$ }

S $\rightarrow$ $S_1$ ; $S_2$  {$S_1.t = S_2.t = S.t;$ $S.s = S_1.s + S_2.s; $ }

Clearly the non-recursive version of the grammer is:

S $\rightarrow$ id = expr T

S $\rightarrow$ if expr then $S_1$ else $S_2$ T

S $\rightarrow$ while expr do $S_1$ T

T $\rightarrow$ ; $S_2$ T

T $\rightarrow$ $\epsilon$

But we also need to change the semantic actions accordingly. Any ideas how this can be done?


texts:
I have a problem that smells like it is NP-complete, but at the same time it feels like maybe you can solve it by just keeping track of column-wise Hamming distance or something, or that it's equivalent to some spanning tree-like problem. The problem is as follows.

We have some binary matrix $M \in \mathbb{F}_2^{n\times k}$ with rank $n$. Let $S_i$ be the matrix constructed by sampling the rows of M $i$ times without replacement. I would like to find

the expected rank of $S_i$
a vector $x \in \mathbb{F}_2^k$ such that appending $x$ to $M$ prior
to sampling will maximize the expected rank of $S_i$.

Any ideas on sources that cover similar problems would also be appreciated.


texts:
This is an assignment of an introductory course of complexity theory and I need to find a way to do the following:

Given $n,m \in \Bbb N$, is $n \le m!$ ?

The idea is to provide a Post Machine that can decide this in an efficient way, using $n,m$ in a binary codification.

We know that the factorial isn't efficient, so the problem actually is just to find a way to decide this, if it's possible.

I know how to compare if $n\le m$, but the factorial is my problem.
I don't how how to compute $m!$ with a Post Machine, if possible, in polynomial-time.

I guess that the most simple way to do this is comparing $n$ with factorials of numbers that are lower than $m$, but the factorial it's still my problem.

My question, is there an algorithm that can help me?


texts: How to come up the number of nodes on a given level in heaps?

texts:
CLRS asked it's readers to prove that there are at most $\lceil n/2^{h+1} \rceil$ nodes of height $h$ in any n-element heap as an exercise. The principle of Mathematical Induction can be used to prove this as explained here.

My question is how one can come up with this formula at first place. Are there any key observations that lead us to this expression initially. And then proof by induction that this will hold true for all positive integer.


texts: A "triangular" data structure for commutative relationships

texts: A multiplication table is symmetric over a diagonal, so only about $n^2/2$ of the elements in an $n \times n$ multiplication table contain unique information. Same goes for addition tables. In fact, the same is true for any table that represents a commutative relationship. Is there a data structure that can take advantage of commutativity to avoid storing redundant values?


texts:
Working for my exam, this question popped up.

  Given the production rules below, draw a pushdown automaton to recognise the language it generates:
  S → AB
  A → BA
  B → BB
  B → T
  T → b

Questions:
1. Since A has no empty transition, wouldn't this just end up in an infinite loop?
2. What order are the values entered into the stack.
If first you enter S, would it then be B at top of the stack and A at bottom or the other way around?
3. Below is my current interpretation of the PDA. Is it correct? Or does the question ask for the transition table?


texts:
Consider that you have a permutation of $n$ elements from $1$ to $n$ and you need to sort the elements lexicographical . for example sorted permutation for $n=11$ is $1,10,11,2,3,4,5,6,7,8,9$ .Now consider this notation $Q(n,k)$ as position of number $k$ in  lexicographical  sorted permutation. $Q(11,2)=4$. We are given $k$ and $m$ we need to find minimum $n$ such  that $Q(n,k)=m$ holds.
I could only find that $n>=max(m,k)$ and for next i do not know how to solve it .
Source of question  link


texts: What's the union between a decision problem and its complement

texts:
I see the union of problems as something like this:
$P=F\cup G$
$P(\omega):$
$\;\;\;\;if\; F(\omega)==True: return \;\; True$
$\;\;\;\;else\;if\; G(\omega)==True: return \;\; True$
$\;\;\;\;else: return\;\; False$
As far as I understand, the complement of a decision problem it's the same problem but with its return values switched.
If I got the above things right, that means that:
$P=F\cup \overline{F}$
$P(\omega):$
$\;\;\;\;return\;\; True$
Are my conclusions correct, is the union of a problem and its complement a problem that always accepts?


texts: Shouldn't the "even parity" function map 1101 to 0?

texts:
From the book Computer organization and design by Patterson&Hennessy:

  Parity is a function in which the output depends on the number of 1s in in the input. For an even parity function, the output is 1 if the input has an even number of ones. Suppose a ROM is used to implement an even parity function with a 4-bit input. Then the contents of the ROM is
  $$\text{Address} \ 0 : \ 0 \\ \text{Address} \ 1: \ 1 \\ \text{Address} \ 2 : \ 0 \\ \text{Address} \ 3 : \ 1 \\ \vdots \\ \text{Address} \ 13 : \ 1 \\ \text{Address} \ 14 : \ 0 \\ \text{Address} \ 15 : \ 1$$

As per my understanding, ROM which implements the even parity function should store 0 at both the Address 1 and the Address 2, 1 at the Address 3, ... 0 at both the Address 13 and 14, then 1 at the Address 15, for the Address $k$ to represent the map-value of $(k)_{\text{base}2}$.

According to this the concept defined above is not clear enough, Can someone clarify the doubt?


texts: What are widely-used, practical applications to come from the study #P problems?

texts:
When, beyond theoretical exercises, do we care how many solutions we can find for something?

I had an analogous question for TMs before - why is it useful to study machines that can only deliver acceptance and rejection as output? Here, the answer (at least in a practical context) seems more clear - find a solution (e.g., a shortest path in a shortest path problem) is a matter of  poly-time reduction to yes/no answers. For #P problems, reduction is equally obvious, but not useful, since you're solving a problem at least as hard.


texts: How to recognize digits in water meter image

texts:
I need to read the digits of images like the one below:

From what I understand, this will involve:

Registering and segmenting the image into each individual digit
Hand labeling a bunch of these individual digit images
Training a classifier based on that hand labeled data
Putting it all together

Am I on the right track? Am I correct in thinking there is no way to read the whole 7 digit integer at once? (Don't care about the decimal.)

If so, can anyone recommend resources on the best way to approach 1?

And what would be the best ML technique for 3?

Many thanks!


texts: Making a profit as a high-dimensional store owner?

texts:
Been thinking about a problem recently and I am wondering if anyone can comment on some ideas to make solutions to this problem more efficient.

Let's say that I am some business owner with a set of $n$ possible store locations $L = \lbrace x_i \in \mathbb{R}^m \rbrace_{i=1}^n$, for $m > 1$, where I'd like to build some new stores. I have estimates that each location $x_i$ will cost $c_i$ to build and should make a corresponding profit $p_i$ after opening. Further, I have a budget of $B$ that I cannot exceed and all stores I build must be at least a distance $D$ away from each other based on the metric $d(\cdot,\cdot)$. My goal is to build stores such that I maximize my profit and stay within the desired constraints. Note that $(L,d)$ is a metric space.

Define $S = (s_1, s_2, \cdots, s_n) \in \lbrace 0, 1 \rbrace^n$ such that $s_i = 1$ means I am building a store at location $i$ and $s_i = 0$ means I am not. It is clear that this optimization problem can be posed as:

\begin{align*}& &&\max_{S \in \lbrace 0, 1 \rbrace^n} \sum_{i=1}^n p_i s_i \tag*{}\\&\text{subject to} &&\sum_{i=1}^n c_i s_i \leq B \\& && d( x_j, x_i ) \geq D \hspace{1cm} \forall j > i \geq 1 \text{ where } s_i = s_j = 1 \end{align*}

Now when looking at this problem, it is quite simple to solve it using dynamic programming if we assume the store locations are far enough apart that the distance constraint is automatically satisfied or the locations are all contained within some 1-dimensional affine subspace. Outside of this, things seem a bit complicated.

My thought is to initially construct a graph $G = (V,E)$ such that $V(G) = \lbrace 1, \cdots, n \rbrace$ and $E(G) = \lbrace ij \;|\; d(x_i, x_j) \geq D \rbrace$. From here, a simple but inefficient idea is to enumerate all cliques of $G$, solve them using dynamic programming, and choose the solution, across all of them, that's the best. This should be fine because each clique, by construction, is comprised of store locations that satisfy the distance constraints and in turn should individually allow for efficient solutions. This might be formalized by defining $\lbrace C_1, C_2, \cdots, C_p \rbrace = \text{cliques}(G)$ as the set of cliques of $G$ and then solving

\begin{align*}& &&\max_{S^{(j)} \in \lbrace 0, 1 \rbrace^n} \sum_{i = 1}^n p_i s_i^{(j)} \tag*{}\\&\text{subject to} &&\sum_{i = 1}^n c_i s_i^{(j)} \leq B\\& &&s_i^{(j)} = 0 \hspace{1cm} i \in V(G) \setminus V(C_j) \end{align*}

for each $j^{th}$ clique $C_j$. From here we then choose $S^* = \arg \max_{j \in \lbrace 1, \cdots, p \rbrace} \sum_{i=1}^n p_i s_i^{(j)}$ as the optimal solution for the overall problem.

Obviously the crappy thing about the above approach is that we have to enumerate all the cliques, which may be both a large set and computationally demanding to find. Is there any structure to the problem I am missing that might make this solvable without enumerating all the cliques in this formulation? Perhaps there's a different perspective that could shed some light?


texts: 2 approximation algorithm for the single machine scheduling problem

texts:
We are given one machine and $n$ jobs that we want to process.

For the $n$ jobs we have the following data:

$r_{1}, ... , r_{n}$ are the release times

$p_{1}, ... , p_{n}$ are the processing times

$d_{1}, ... , d_{n}$ are the deadlines/due dates

$c_{1}, ... , c_{n}$ are the completion times(when the jobs are finished executing)

$l_{1}, ... , l_{n}$ are the latenesses achieved where $l_{j} = c_{j} - d_{j}$

Our goal is to find a schedule that minimizes the maximum lateness achieved ($L^{*}_{max}$)

Since even deciding whether there is a schedule such that $L^{*}_{max} \leq 0$ is np hard, this implies that we can not come up with an approximation algorithm of any ratio $\rho > 0$ that runs in polynomial time and produces a schedule with maximum lateness at most $\rho L^{*}_{max}$. So this is why we make the assumption that the due dates are negative, ie $d_{i} < 0$

Before trying to come up with an algorithm, we can prove that for any subset $S$ of jobs, $L^{*}_{max} \geq r(S) + p(S) - d(S)$ where $r(S) = min_{j\in S}r_{j}$, $p(S) = \sum_{j\in S}p_{j}$ and $d(S) = max_{j \in S} d_{j}$.

To prove this what we have to do is look at the last job of the optimal schedule and try to find its lateness, which will also be a lower bound for the maximum lateness achieved.

Now, having this as a fact for any schedule, assume our algorithm produces a schedule as follows. At each moment the machine is idle, start processing next the available job with the earliest due date.

The analysis I have in my book (the design and analysis of algorithms by Williamson and Shmoys) is as follows:

We consider the schedule produced by our algorithm and let $j$ be the job of maximum lateness in the schedule. That is $L_{max} = c_{j} - d_{j}$. We focus on the time $c_{j}$ in this schedule and try to find the earliest point in time $t \leq c_{j}$ such that the machine was processing without any idle time for the entire period $[t, c_{j})$. By our choice of $t$, we have $r(S)=t$. Let $S$ be the set of jobs that are processed in that interval. From the bound about the maximum lateness we found before, we have that $L^{*}_{max} \geq r(S) + p(S) -d(S) \geq r(S) + p(S) = t+p(S) = c_{j}$

Then we only focus at the last job $j$, so we get $L^{*}_{max} \geq r_{j} + p_{j} - d_{j} \geq -d_{j}$

combining both the equations we get $c_{j} - d_{j} \leq 2L^{*}_{max}$

what I don't understand is, where do we actually need the earliest due time rule?  Where do we use it in the analysis? What would happen if we used the longest due time rule? Could we then apply the same analysis to come up with the same approximation ratio?


texts: Why is quicksort better than other sorting algorithms in practice?

texts:
In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ in the worst case (like mergesort and heapsort), and even linear time in the best case (like bubblesort) but with some additional needs of memory.
After a quick glance at some more running times it is natural to say that quicksort should not be as efficient as others.
Also, consider that students learn in basic programming courses that recursion is not really good in general because it could use too much memory, etc. Therefore (and even though this is not a real argument), this gives the idea that quicksort might not be really good because it is a recursive algorithm.
Why, then, does quicksort outperform other sorting algorithms in practice? Does it have to do with the structure of real-world data? Does it have to do with the way memory works in computers? I know that some memories are way faster than others, but I don't know if that's the real reason for this counter-intuitive performance (when compared to theoretical estimates).

Update 1: a canonical answer is saying that the constants involved in the $O(n\log n)$ of the average case are smaller than the constants involved in other $O(n\log n)$ algorithms. However, I have yet to see a proper justification of this, with precise calculations instead of intuitive ideas only.
In any case, it seems like the real difference occurs, as some answers suggest, at memory level, where implementations take advantage of the internal structure of computers, using, for example, that cache memory is faster than RAM. The discussion is already interesting, but I'd still like to see more detail with respect to memory-management, since it appears that the answer has to do with it.

Update 2: There are several web pages offering a comparison of sorting algorithms, some fancier than others (most notably sorting-algorithms.com). Other than presenting a nice visual aid, this approach does not answer my question.


texts:
I need to prove:

XY + ~XZ + YZ = XY + ~XZ

I cannot think how to do this.

I have tried factorising, but I just don't know of any rule that removes one of the terms like above.

I start with the LHS, naturally:

All I can do is get to:

Y(X+Z) + ~XZ