texts: Find a path from s to t using as few red nodes as possible

texts:
Was doing a little interview prep. Given an undirected graph G, such that each node is colored red or blue and |E|≥|V|, find a path in O(|E|) time such that starting and ending at 2 blue nodes, s and t, that you pass through as few red nodes as possible.

Initial Impressions: Since |E|≥|V|, O(|E|) time would include O(|E|+|V|), which means the solution likely uses BFS or DFS. Modifying the graph such that causing the all red nodes must be forced down a directed path of some long length (after making the whole graph directed) in order to use out-of-the-box BFS seems not viable, as it would mean constructing a new graph would be along O(|E||V|) time.

Another method I toyed around with was propagating values to nodes based on the safest path to that node while doing a DFS search, but not all values were guaranteed to update.

I still want to try to solve this myself, but I'm really stuck right now. Was wondering if there were any hints I could get. There are much simpler ways of doing this if it weren't for the O(|E|) time. Djikstras with creating some edge weights would work, but wouldn't be within the time bound.


texts: Find the recurrence relation for the following algorithm

texts:
The question requests to find the recurrence relation of the following algorithm and solve it using the characteristic equation.
\begin{align}
&\text{SORT}(A[0\dots n-1])\colon\\
&\quad \text{if } n = 2 \text{ and } A[0] > A[1] \text{ then} \\
&\quad\quad \text{swap}(A[0],A[1]) \\
&\quad \text{else if } n > 2 \text{ then} \\
&\quad\quad m=\lceil 2n/3 \rceil \\
&\quad\quad \text{SORT}(A[0\dots m-1]) \\
&\quad\quad \text{SORT}(A[n-m\dots n-1]) \\
&\quad\quad \text{SORT}(A[0\dots m-1])
\end{align}
The recurrence equation that I found is $T(n) = 2 \cdot T(2n/3) + T(n/3) + 1$ with base case $T(2) = 5$.
The base case is $T(2) = 5$ because of 2 comparisons in the if statement plus 3 statements in swap() function.
I'm not sure whether what I've tried is correct or not.
All help is appreciated!


texts:
I'm reading Fischer et al.'s Impossibility of Distributed Consensus with One Faulty Process, and I don't quite follow 2 points:

The first is in the proof of Lemma 3, pg. 378:

  Otherwise, $e$ was applied in reaching $E_i$, and so there exists $F_i ∈ \mathscr{D}$ from which $E_i$ is reachable.

Why does there exist $F_i ∈ \mathscr{D}$ from which $E_i$ is reachable?

The second is more general: what does having at most one faulty process have to do with the theorem that "no consensus protocol is totally correct in spite of one fault"? In the part where

  We now show that it is always possible to run the system in a way that avoids such steps, leading to an admissible nondeciding run.

I don't see anything depending on having at most one faulty process. In fact, what would change if no process was faulty?


texts: Reduction function from A to its complement

texts:
I wanted to ask a simple question.

Lets say we have A, language of all the words with more then 3 letters. so it belongs to R.

and its complement , is the language of all words with less then 3 letters.

is it possible to say that I can define a turing reduction between them?

i thought about something like this:
$$
f(x) = \begin{cases} 01 & \text{if }x \in A, \\ 1234 & \text{ } else.\end{cases}
$$

my friend is saying this solution is not good since, the definition is:
$\qquad\displaystyle x \in L_2 \iff f(x) \in L_1$

and what i got is

$\qquad\displaystyle x \notin L_2 \iff f(x) \in L_1$

If in this case it wont work can you explain me why?
Thank you!


texts:
I'd like to as a variation on this question regarding Huffman tree building. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without drawing tree.

Specific Example is : 10-Input Symbol with Frequency 1 to 10 is 5. the above question mentioned depth is 5.

I read about max depth of Huffman and Entropy, but not well description for me.

Edit:

We know in my specific example the frequency is: $1$ to $10$ which means probability is: $(1/55)+(2/55)+(3/55)+(4/55)+(5/55)+(6/55)+(7/55)+(8/55)+(9/55)+(10/55) = 1 $


texts: Randomly selecting element from data structure, probability based on weight

texts:
I have a list of elements, each with an id and a weight.
A: The weight should be directly proportional to the probability of being randomly selected: An element with weight 10 should be twice as likely to be selected as an element with weight 5.
B: I need to add/remove elements and increase/decrease their weight dynamically.
I have already found a solution, if I exclude B:
1. fill array with id and weight
2. compute prefix sum
3. generate random number r between 0 and sum of weights - 1
4. binary search which element in the prefix sum corresponds to r

Let n be the number of elements, this solution would be able to retrieve the desired element in O(log(n)), precomputation is O(n). However I cannot add/remove elements or alter their weight without having to precompute the prefix sum again.
Can someone provide me with an approach working for A and B? I have tried using a segement tree but don't find a satisfactory solution.


texts: Why is the second operation of a Monad called bind?

texts:
I understand how monadic computation works, I am just wondering where does the name come from. I cannot relate the thing that the bind operator actually does (i.e. unbox the monadic value, and then apply a function to produce another monadic value) and the name bind (which, to me, means associate two things together).

I understand why we have the name return (I suspect it has to do with the Haskell do-notation), although IMHO it isn't a good name either. Return indicates a change in control flow but it really isn't, all it does is produce a monadic value.


texts: If Turing Machines are the automata equivalent of the $\lambda$ calculus, what is the automaton equivalent of the $\pi$ calculus? I suppose it would be some class of automata that resembled a Turing Machine, but with support for communication channels or signals of some type, but I'm not sure, and would appreciate some direction.


texts: How to solve this recurrence using recursion tree method

texts:
How to solve this using the recursive tree method? I'm stuck with the $\max$.

$$T(n) = T\left(\left\lceil \frac{n}{\max\,\{\sqrt{n},2\}}\right\rceil\right) + n\,.$$


texts: Finite automaton for $\{0^{2n} : n \ge 0 \} \cup \{(100)^m : m \ge 0\}$

texts:
I have to construct an FA for the following language:
$$
\{ w_1,w_2 \in \{a,b\}^* \mid w_1 = 0^{2n}, w_2 = (100)^m, \text{ for some } n,m \in \mathbb{N} \}.
$$
Does anyone here have any experience with something like that? I'm totally lost how I should draw an FA for something like that. Would appreciate any kind of input or approach to this problem.


texts: How to partition disagreeable people into compatible groups

texts:
We have a number of people that must be partitioned into groups, but there may be people that dislike other individuals.   Partition the people into the minimum number of groups such that no person is grouped with someone they don't like.  (If A doesn't like B then A cannot be in a group with B. Each person must belong to exactly one group.)

The incompatibilities between people are given explicitly as unordered pairs of people that cannot be in a group together.

Consider one possible scenario involving 10 people where incompatibility pairs are given as follows:

(1,2) (1,6) (1,7) (2,3) (2,6) (2,7) (2,8) (3,4) (3,7) (3,8) (3,9)
(4,5) (4,8) (4,9) (4,10) (5,9) (5,10) (6,7) (7,8) (8,9) (9,10)

In this scenario it is unacceptable to form a group consisting of persons [ 1, 4, 5 ] because of the incompatibility pair (4,5), which means that persons 4 & 5 are incompatible and cannot be in the same group.

For the scenario given above, we can divide people up optimally into groups that all get along, using no fewer than 4 groups.  Here is one such way of arranging people into 4 groups.

GROUP #1 : [ 1, 3, 5 ]
GROUP #2 : [ 2, 4 ]
GROUP #3 : [ 6, 8, 10 ]
GROUP #4 : [ 7, 9 ]

Note, that the groups do not have to have the same number of members, and it is acceptable to have a group consisting of only one individual if necessary.  But each person must assigned to a group.

Describe an algorithm, given an arbitrary incompatibility matrix among N people in the form of zero or more incompatibility pairs, to determine a compatible grouping that uses the fewest groups possible.

EDIT:  Here's what I have tried so far.

A greedy algorithm:

While there are persons not yet assigned to a group.
   Take the lowest numbered unassigned person and create a new group `g` consisting of just them.
   For each person `p` not yet added to a group:
       If they are not incompatible with anyone in the current group `g`:
          Add person `p` to group `g`

I have no confidence at all that this would produce the minimal number of groups though.


texts: Not respecting the 3rd rule of a LL(1) grammar

texts:
I'm trying to build a grammar that violate only the 3rd rule. I'm trying to figure out what kind of grammar would not respect that.

I think the grammar has to be left-recursive to not respect it.

if $\beta \Rightarrow^* \epsilon$ then $\alpha$ does not derive any string beginning with a terminal in $\mathop {FOLLOW}(A)$. Where $A \to \alpha \mid \beta$

Am I right to think that?


texts: Let $G=(V,E)$ be a simple graph with weights $w_{ij}$ (can be assumed to be positive). Is it possible to find the minimum (or maximum) weight, rooted spanning tree that is binary? That means every node has a degree at most 3, which would correspond to a parent and two children?


texts: Maximum weight tree with weights on vertices

texts:
Problem Statement

Let, $G(V,E)$ be a graph with a weight function $w(v)$ defined for all vertices. We need to find a tree $T(V',E')$ such that the resulting tree have maximum sum of weights of vertices, where $V' \in V$ and $E' \in E$. In short, we need to remove some vertices(along with all their edges) from $G(V,E)$ such that the resulting graph is a tree and have maximum weight among all such trees. $T(V'.E')$ should be an induced subgraph of $G(V,E)$.

My Attempt

First, sort the vertices in descending order. Then, pick the vertices in that order ensuring that adding a vertex won't create cycles. If it creates cycles, don't consider that vertex. To check if adding a particular vertex adds cycles, I thought of assigning each component a uniaue number. Hence, if adding a vertex results in joining that vertex to two vertices of the same component, we don't add that vertex. But, I couldn't find an efficient way on how should we keep track of which vertex belongs of which component. Can DSU help me with this approach?


texts: Omission of smaller variables in Big-O Complexity

texts:
I have an algorithm that:

1. takes in a book's text as a string.

2. splits that string into words and stores it in a list.

3. creates a hash table from this list by iterating over the elements of the list

4. It then iterates over a separate list of words to see if each of these words (in this separate list) is contained in the hashmap.

Three linear traversals occur here. One to split the input string into a word list, one linear traversal of the word list to create the hash table and one final traversal over the separate list to check each word is in the newly created hash table.

Time complexity is O(n + k + m), where n is the number of characters in the input string, k is the number of words and m is the number of words in the other list.

My question is, since k is derived from n and we can guarantee that k will always <= n can we omit n and write the complexity as O(n+m)?


texts: Does anyone know whether universal queue automata have ever been considered, and, as for Universal Turing Machines, some "small" universal queue automata are known?


texts:
In type theory, some inductively defined data types allow you to prove absurdity. For example

type Bad a = MkBad (Bad a -> a)
extract : Bad a -> a
extract val@(MkBad f) = f val
absurd : a
absurd = extract (MkBad extract)

Now, when you church encode this datatype it leads to

badChurch : Bad a -> (forall X. ((X -> a) -> X) -> X)
badChurch _ = ?

Now, it seems to me that this function type is actually uninhabited and my intuition says that it could be proven using Theorems for free but alas I can't find a way to actually do that.

The deeper question is this: Would showing the existance of a church encoding be enough to prove consistency of a datatype? And contrary; Are there datatypes whose church encoding is uninhabited with which you can not prove absurdity?

Pretend you want to check if you allow a datatype in your language. Would it be enough to check if the type's church encoding exists to safely allow the type in your language?


texts: How does hashed inverted page table work?

texts: I understand hash function and inverted page table, but then the book I read describes something called hashed inverted page table (use hash to accelerate the finding because IPT is large), with TLB used. I don't understand why there is an arrow point to itself inside the hash table? Could anyone explain the mechanism?


texts: If a parser can parse a non-deterministic grammar, is the parser non-deterministic?

texts:
I've written a recursive-descent parser generator, and I'm trying to classify it (call me a cowboy coder if you must). According to wikipedia, S → 0S0 | 1S1 | ε, which checks for an even-length palindrome, is a non-deterministic grammar. My parser generator can handle this grammar. Does that mean my parser is non-deterministic?

To be honest, I'm not even sure that it's proper to try to classify it like this. It doesn't really match the description of a pushdown automata, since it passes data up and down through the stack (parameters, passed by reference, which may be modified). If anyone would be interested in taking a closer look at it, I'd be most grateful. It handles left recursion and ambiguous grammars in (I believe) polynomial time and space. https://github.com/coder0xff/parlex


texts: Efficiently remove nodes from a connected graph

texts:
Suppose you have a connected graph and want to remove k nodes such that the result is still connected.  How could you do this efficiently?

It occurs to me that you could find any spanning tree, say by a tree search of any kind.  Identify all leaves in the spanning tree, all of these can be removed without disconnecting the remaining vertices.  If you have more than k leaves then you're done, but in any tree you're only guaranteed 2 leaves.  So you may need to reiterate the process until you've removed k vertices.

That implies O(k) runs of a tree search. Does a more efficient algorithm exist? I don't think you can just look for articulation points or bridge edges because removing a single vertex may suddenly make other vertices which weren't articulation points now turn into articulation points.


texts:
Under Huffman Encoding, what circumstances codeword length  of each character
be equal?(suppose number of character is power of 2)

I think if all frequency of characters is same then codeword length of all characters be the same.
Surprisingly, if there are two characters that differences between frequency of two characters be $2$, and frequency of other be equal then codeword length of all characters be the same.
Main problem is, can i say, for each constant $c$, if there are two character that difference of  frequency be $c$, and all remaining of characters  have equal frequency then codeword length  of each character be equal?


texts: Finding fewest strings that cover $\Sigma^n$ up to $R$ edit operations

texts:
Let $\Sigma$ be the alphabet, $0<R<n$ be an integer and let $\Sigma^n$ denote the set of all strings of length $n$ over the alphabet. The task is to find the minimum $m$ such that there exist strings $S=\{s_1, \dots, s_m\}\subseteq \Sigma^n$ that satisfy:
$$\forall x\in \Sigma^n\;\; \exists y\in S\colon ED(x,y)\le R$$
In other words, we want to minimize $|S|$, such that any string of length $n$ can be constructed from them with at most $R$ edit operation.

Let $S^\star$ denote one optimal solution. My guess is that an algorithm computing an optimal solution is not efficient, and likely to grow as a function of $|\Sigma|^n$. My question is, is it possible to compute an approximate solution, say satisfying $|S|\le 2|S^\star|$, in time polynomial in input size $\mathrm{Poly}(|\Sigma|,m,n)$?


texts:
I have a hashtable with length $m$. Initially it's empty. Next, $n/2$ unique random numbers $\in [0, n]$ are added to it.
What would be variance of chain length when such $n/2$ numbers are being added $x$ times?
I tested it using code with $n=2^{16}$, $m=2^{15}$ (part of md5 was used as index) and got the following results:
$$
\begin{array}{|l|r|r|r|r|} \hline
x & 1 & 2 & 3 & 4 \\\hline
\text{Variance} & 2 & 6 & 12 & 20 \\\hline
\text{Mean} & 2 & 4 & 6 & 8 \\\hline
\end{array}
$$
How can I calculate these values without testing, or what is the probability of a value being added into a specific index in the table?
Hash table looks like following:

Second variant
Given table with size of $m$ (let it be $table_1,\ldots,table_m$). Initially it filled with $0$.
Next, I am inserting values into it: I choose $n/2$ different random numbers ($a_1,\ldots,a_{n/2}$) between $0$ and $n$ .
For each of the chosen numbers I am calculating hash (using SHA) $h_i$ with size of $m$:
$$
h_1=hash(a_1),...,h_{n/2}=hash(a_{n/2})
$$
Calculated hash is the index for the table. For each calculated index I am increasing value in the table by $1$.
$$
table_{h_1}=table_{h_1}+1,...,table_{h_{n/2}}=table_{h_{n/2}}+1
$$
What would be variance of the values in the table ($table_1,\ldots,table_m$) if I do that insertion $x$ times?
In the example result I am calculated variance like this:
$u_1,...,u_k$ - unique values from the table ($table_1,\ldots,table_m$)
$p_1,...,p_k$ - probability of appearance of the corresponding unique number $u$ in the table
$Var = \sum_{i=1}^{k} p_i(u_i-mean)^2$


texts:
I've recently started casually reading into combinatorial logic, and I noticed that a higher-order function that I regularly use is a combinator. This combinator is actually pretty useful (you can use it to define addition on polynomial equations, for example), but I never gave it a decent name. Does anyone recognise this combinator? (ignoring differences in function currying)

unknown = function (h, f, g)
    function (x) h( f(x), g(x) )
}

In lambda calculus, the fully curried implementation would be
$\lambda h. \lambda f. \lambda g. \lambda x. h (f x) (g x)$. In other words, if $M$ is this mystery combinator, then its defining equation is $M \, h \, f \, g \, x = h \, (f \, x) \, (g \, x)$.

If more information is needed, or my question is lacking key information please leave a comment and I will edit my question.


texts: “In object-oriented programming, the program is organized around its data”

texts: In a description of OOP in my textbook, it is written that “in procedure oriented program the program is organized around its code while in object oriented programming, the program is organized around its data”. What is the meaning of this statement? An explanation with an example would be of great help.


texts: How much time would be needed to compute an algorithm with time complexity $O(n^k)$?

texts:
How much time would be needed to compute a minimum k-cut, which has time complexity $O(n^k)$ on a graph with $n=5000$ and $k=30$? Consider using a basic 2GHz and 8GB RAM laptop.

Please explain also the process of how to compute the answer.


texts: Why mantissa and exponent are stored differently in a float?

texts:
As we know, in IEEE 754 standard, float number's exponent and mantissa are stored differently. While the exponent is stored as an unsigned number, taking advantage of the bias, the mantissa is in sign-magnitude format.

The reason to use a bias seems to be the fact that another value of exponent can be achieved this way, effectively providing a considerable amount of "new" numbers that can be represented (2^24 for 32 bit floats).

On the other hand, using the same system in mantissa would provide only 2^8 new values which, given the whole range of a 32 bit number, is nothing.

For humans, it would obviously be much more difficult to read float numbers with mantissa expressed the same way the exponent is.

Is that the sole reason against such notation?

Isn't a unified notation system, simplified arithmetics and a tiny bit larger range worth the hassle?


texts: Why is the consensus number for test-and-set, 2?

texts:
According to Wikipedia,

  The test-and-set operation can solve the wait-free consensus problem for no more than two concurrent processes.

Why can't it solve the problem for more than two processes?


texts: Is it admited to give the complexity of a function regarding the resulting data structure?

texts:
Assume that we have a data structure which uses $O(\log n)$ space to store an integer $n$ and has a function $f$ which replaces the integer $n$ stored by $2^n$, i.e. $n=2^n$.

The time complexity of $f$ is $O(n_{_{old}})$ = $O(\log\ n_{_{new}})$,
is it admited to say that $f$ is a $O(\log n)$ function ?


texts: Adding Big-O and little-o notation to get a little-o

texts:
Lets suppose that there exists a comparison-based algorithm that turns an arbitrary array to a state $A$ in $o(n\log k)$, and there is another comparison-based algorithm that turns an array in state $A$ to completely sorted in $O(n\log (n/k))$. $n$ is the size of the array, while $k$ is another non-constant parameter given. I want to get a contradiction. Here is my reasoning:

Running the first algorithm followed by the second completely sorts the array, and takes

$$o(n\log k)\ +\ O(n\log(n/k)) = o(n\log k\ +\ n\log(n/k)) =$$
$$o(n(\log k\ +\ \log(n/k))) = o(n\log (k \times n/k)) = o(n\log n)$$

which is a contradiction to the known lower bound to comparison-based sorting algorithms.

My question is: Is my reasoning correct? Why or why not? I've tried to prove it using the definitions, but I'm stuck.

Thanks.


texts: Example of non-regular context free language L such that prefix(L) is regular

texts:
Suppose we have some non-regular context free language L. Suppose we also have language of all prefixes of words in L.

  What can be an example of non-regular language L such that language of
  it's prefixes is regular (Can be represented by a finite automaton)?

I don't understand how language of prefixes can ever be regular, since the set of
 prefixes of a word include the word itself.

For example $L= a^nb^n$ is my non-regular language.
The language of it's prefixes would include : $\epsilon,a^n$ where $n\ge 1$,$a^nb$ where $n\ge 1$ etc...

But what about b's ? We need to know how many a's there were in the first place. Therefore I don't see how the language of prefixes can be regular.


texts: Check which interval range does a number lie in between

texts:
I have an array of time variables t(1), t(2), ..., t(n). and corresponding variables v(1), v(2), ..., v(n). Given a time tx, I would like to efficiently find between which interval (t(i), t(i+1)] does the number lie. Correspondingly, the variable vx needs to be interpolated which can be done easily afterwards.

P.S: The time t(i=1) is initialized with t1 and is always increasing and greater than zero.


texts:
Let M be a deterministic Turing machine wich has the properties:

1) $\forall x,y \in \Sigma^* : t_M(xy) \ge t_M(x) + t_M(y)$

2) $\forall a \in \Sigma: t_M(a) \ge 1$
 (Also 2) should be obvious for every DTM).

Then it follows that for all $x \in \Sigma^* : t_M(x) \ge |x| $.
The graph $G_M$ induced by the transition function contains a cycle:
To see this choose a word $w$ whose length $|w|$ is $> |Q|$ where $Q$ is the set of states of $M$. Then we have $t_M(w) \ge |w| > |Q|$. Since $M$ is at every time step on exactly one state, $M$ must visit in $t_M(w) > |Q|$ time steps one state at least twice, hence the graph $G_M$ must contain a cycle.

My question is this:
Can we construct to every DTM $M'$ an equivalent DTM $M$ with the properties above?
In my intuition this is possible: Just construct $M$ such that it reads all the input, writes what it has read, move the pointer to the beginning of the word and then gives control to $M'$. But is it possible to give a more formal proof for this? Or is my intuition wrong?


texts: Relation between Parameterized complexity and Approximation Algorithms

texts:
I want to know whether there is a relation between parameterized algorithms and approximation algorithms.

Like there will exist a fpt problem for problem P iff it have some f-approx algorithm.

I would be also happy if some one can give me reference.

Edit: It's just observation from my aspect that c-approx algo have fpt algo where c is constant. I am not able to prove it but I want contradicting example.

Also this implies there is a relation between kernel and the approximation algo.


texts: Integrality gap in Online Problems and adaptation to competitive ratio

texts:
As we all know, in offline problems it is common practice to calculate the integrality gap to get some bound on the approximation ratio of the integral solution.

Now this gap ($IG:=\frac{OPT_{frac}}{OPT_{int}}$) relies on the fact that we can compute the fractional optimum by just solving the relaxed linear program of the problem.

In Online Algorithms there is no LP which can be relaxed and solved. Well there technically is but we can't solve it like we do in the offline setting, since online algorithms must make decisions irrevocably and without knowing what to come.

So maybe we are lucky and we can approximate a fractional solution online (by a factor of $\alpha$) and round this solution with the loss of the $IG$ (also online) to get some integral solution for our problem.

My question is, how we can adapt the knowledge of our offline setting to the online setting.

As a matter of fact, can we just conclude that if we have a online $\alpha$-approximation for the fractional online problem, that we could (at most) have some $\frac{\alpha}{IG}$-approximation by rounding.

Thanks in advance


texts: What is the metadata in microblogging platform?

texts:
I'm reading papers regarding microblog credibility perception of non-text cues.

Tweeting is believing? Understanding microblog credibility perceptions
by Morris et al., 2012
Microblog Credibility Perceptions: Comparing the United States and China
by Yang et al., 2013

However, Yang et al.[2013] refer to some cues, such as location, number of followers, is a reply as metadata. Metadata is defined as 'data about data', but such cues seem normal data to me.

Examples of cues mentioned:

author location
contains URL
number of followers
is a retweet

Now I'm confused what exactly does metadata include in microblogs, and what is the difference between metadata and normal data in microblogs.

For example:
the number of followers - it's a non-text data. But is it a data or metadata?


texts: Expected Linear time Minimum Spanning Tree algorithm

texts:
I am trying to understand the proposed "Randomized Linear-Time Algorithm to Find MST".

My findings:
I have read and search almost every available resource( main paper, wiki, reports on paper, lecture on paper ) but not getting any clue regarding my confusion.

Question:
In the original paper Section 3: The Algorithm "Step 2" says "In the contracted graph, choose a subgraph H by selecting each edge independently with probability 1/2."

If I have 6 vertexes with 14 edges. And if I choose 7 edges with probability 1/2 then there might be some isolated vertex. In that case, what will happen to that isolated vertex?


texts: Minimal Steiner Tree in unweighted directed graph

texts:
I have an unweighted directed graph $(V, E)$ and a subset $T \subseteq V$ of these vertices. I want to find the minimum tree $(V',E')$ that contains all these $T$ vertices (minimize in number of nodes $|V'|$).

In my problem all vertices $t \in T$ have no leaving edges:
$$\left\{(t,w) \in E \mid t \in T\right\}=\emptyset$$

This is a specific case of the Directed Steiner Tree problem.

What's the best algorithm and it's complexity to find the exact solution to the Directed Steiner Tree problem? (Or, if there is, a better solutions to this specific case of the Directed Steiner Tree)

What are the most used approximations for this problem?


texts: Paths between tuples, MSV, decision trees

texts:
I'm reading about Multiset Size Verification Problem and in the following paper - http://www.skynet.ie/~sos/mapviewer/docs/Voronoi_Diagram_Notes_2.pdf - I got stuck just on the first lemma. However, since my concrete problem is rather specific, I'll describe it as self-contained, so that no background in terms of what MSV really is will be needed (but I encourage you to check it :)).

Fix natural $k, n$ such that $k \le n$.
Let $$ Y = \{ (z_1, z_2, \ldots, z_n) \in \mathbb{R}^n :  |\{ z_1, z_2, \ldots, z_n \}| = k \} $$
Next, let $$ T = \{ (z_1, z_2, \ldots, z_n) \in \mathbb{R}^n : \{z_1, z_2, \ldots, z_k \} = \{1, 2, \ldots, k \} \  \text{and} \ z_i \in \{1, 2, \ldots, k \} \ for \ i \in \{ k+1, \ldots, n \} \} $$
In the paper that I linked to, they claim that for any distinct $a, b \in T$, on any continuous path from $a$ to $b$ we must encounter a point $p$ that is outside $Y$, i.e. $p \in \mathbb{R}^n - Y$. Apparently, it is not hard to see that, but I have a big difficulty proving it formally.

I wasn't sure whether to ask this question on Math community, or here, since the problem itself is purely mathematical. It's closely related to CS, though.


texts:
Algorithm question:

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
Example 1:
Input: [0,1] Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
Example 2:
Input: [0,1,0] Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Original source: https://leetcode.com/problems/contiguous-array/
This question reminded me of prefix-sum questions i had done before.
Given array nums:
sum(nums[0:i]) + sum(nums[i:j]) = sum(nums[0:j])

So I figured:
Assuming 2*sum(nums[i:j]) =  len(nums[i:j])-> always True for valid subarrays,

2sum(i:j) = 2(sum(0:j)- sum(0:i))

(j-i+1) = 2(sum(0:j)- sum(0:i))

-i+2sum(0:i) +1 = 2sum(0:j)-j

But it looks like Im having trouble with the code assuming this. I was excited to separate the i and the j (indexes) so that i can hash like so:
        key: -i+2sum(0:i) +1,      value: i
        check for the key with our j value later,
        then do j-i+1
        then compare that to a running global max.

Code:
        d = {}
        sum = 0
        m = 0
        for j in range(len(nums)):
            sum += nums[j]
            if 2*sum - j in d:
                i = d[2*sum - j]
                m = max(m,j-i+1)
            if 2*sum-j+1 not in d:
                d[2*sum-j+1] = j
        return m

It does not work on this input:
[1,0,0,1,1,0]-> output is 4 instead of 6

I think there might be some sort of indexing issue.


texts:
I am trying to implement a secure elecetronic voting system. Therefore I found the Damgard and Jurik Cryptosystem. In their paper the authors describe a secure protocol for "A Length-Flexible Threshold Cryptosystem with Applications" (PDF).

I am an experienced Java programmer with more than 10 years of professional experience. But my math and number theory is a bit rusty. :-) So I do have some questions about the math details of the paper:

In chapter 5 Damgard and Jurik describe a "Self-Tallying Elections with Perfect Ballot Secrecy". I already have implemented the Voter Registration in the Setup Phase. But I do not quite understand the formular (algorithm) for encrypting a vote.  In Chapter 5.1 the paper says:

  The voter i publishes the encryptions
  $$c_{ij} = (G_{ij}, H_{ij}) = E^\pm_{s,pk_j}(s_{ij}, r_{ij})$$
  for all $j \in R_0$ along with a proof, that these are indeed legal encryptions and the sum of the plaintexts is $0 \space mod \space n^s$.

In a previous chapter (on page 10) a function $E^\pm_{s}$ is defind as

  $$E^\pm_{s}(m,r,b_0,b_1) = \\
    ((-1)^{b_0} g^r)\space mod \space n, \space
     (-1)^{b_1} (h^{4 \Delta^2 r} \space mod \space n)^{n^s} (n+1)^m \space mod \space n^{s+1}) $$

Most of the variables are defined. But not all of them.

My questions

As you can see, the paper doesn't exactly define the function $E^\pm_{s,pk_j}$. It only definces a (similar but not equal) function $E^\pm_{s}(m,r,b_0,b_1)$.  => How should I use the private key $p_{ki}$. Which values shall I use for the parameters $b_0,b_1$ ?
What is $G_{ij}$ ? Is that a number or a function?
What is $H_{ij}$ ? Is that a number or a function? What is the variable "h" in the formula for encryption? It is defined nowhere in the paper.

Or on general: Can someone please describe the protocoal (the algorithm) for casting votes in a way, so that it can be implemented in Java?   I am not interested in in any mathematical proofs. I'd just like to implement this.


texts: What is the Big O of computing the natural logarithm of a number?

texts:
I was wondering what the time complexity of computing the natural log of a number is.

Note: I realize that the natural log of number is irrational, so my rephrased question would be "What is the Big-O of approximating ln(x) to d-decimal places?"


texts: How do merged lookahead sets help LALR parse more grammars than SLR?

texts: From what I have searched on Google so far, the only difference between LALR(1) and SLR(1) is that LALR(1) uses states with merged lookahead sets. One source says that LALR(1) won't run into shift-reduce conflicts because the parser will "remember" from which state it arrived at the current state. However, there are no differences in the parsing algorithm, so I'm having trouble seeing how these merged lookahead sets would help the LALR parser resolve shift-reduce conflicts. And if the parser remembers from which state it arrived at the current state, why is it still vulnerable to reduce-reduce conflicts?


texts:
I have to create a roadmap for the quantum computing technology. Looking around I found the timeline on wikipedia that is pretty wide but does not highlight the key events in quantum computing research neither sets the possible future for research.

Could somebody help me to define which are key events in the quantum computing fields? When (and why) we started to explore this technology, for which milestones we passed through and (maybe) what we can set as future milestones?


texts: How did early computers handle variable word length?

texts:
So quoting from the book: A History of Modern Computing (History of Computing)

The introduction of reliable core memory made it practical to fetch data in sets of bits, rather than one bit at a time. That meant a block size or word length, of from 30 to 50 bits.
Business-oriented computers could use shorter word length or a variable word length.
IBM 1401 used an extra bit appended to each coded character to indicate whether or not it was the last one of a word.
The 702 used a special character that signified that the end was reached.

I am not sure if I understand how variable word length works for any of these computers mentioned above.
For the case of IBM1401, what is meant by a 'coded character' and how can a single bit give the information that the end of a word is reached? (Assuming the computer runs on binary..?)
And for 702, what is meant by a 'special character'?


texts: Why is a primary node needed in pBFT algorithm for consensus?

texts: Why is primary needed in pBFT algo? Since many issues of viewchange etc. come up because primary may be faulty - is it possible to have a version of pBFT which doesn't have nodes assigned as primary? Or does having a primary node fulfill a function which is crucial?


texts: DFA/NFA/ε-NFA: subsetting each other or different sets?

texts:
I know that an ε-NFA (NFA with epsilon transitions) is not an NFA or a DFA and an NFA is not a DFA.

HOWEVER, say you have a complete DFA. Isn't that theoretically an NFA and an ε-NFA? Just because it doesn't have ε transitions, does it mean it is not ε-NFA? If a question asks you to turn a DFA into an ε-NFA, can't you just write the complete DFA as an answer? What properties make DFA different from ε-NFA and NFA?

The same question applies to NFA → ε-NFA, isn't NFA a more "primitive" version of ε-NFA? It's just NFA without the ε...


texts: How did each class of languages receive their name?

texts:
If we look at the Chomsky hierarchy, we see that there are four well-known classes of languages: regular languages, context-free languages, context-sensitive languages, and recursively enumerable languages. There's also the class of recursive languages (which fits in between CSL and RE), but Chomsky didn't include this class in his hierarchy for whatever reason.

How did each of these classes receive its name? For instance, what does "recursively enumerable" mean in the context of a Turing machine being able to construct a RE language? What is context, and what differentiates "freeness" from "sensitiveness"? I can imagine that a language is "regular" because it can be generated by a regular expression, but I'm not sure if this is the reason behind the name.

(And a bonus question just for the fun of it: why didn't Chomsky include recursive languages in his hierarchy?)


texts:
Please consider the following probability density function of two variables.
\begin{eqnarray*}
f(x_1,x_2) &=& \begin{cases}
    2(x_1+x_2) & \text{for} \,\, 0 \le x_1 \le x_2 \le 1\\
    0 &\text{ otherwise } \\
    \end{cases}
\end{eqnarray*}
I would like to generate two random values $X_1$ and $X_2$ such that there
distribution is consistent with the above probability density function.

If the above probability density function was of just one variable, then I would solve the above problem with the following steps.
1) I would  find the distribution function $F$ by integrating.
2) I would generate a random number $a$ on the interval $[0,1]$ using the
uniform distribution.
3) I would find a number $X$, such that $F(X) = a$. Then $X$ would be the
random number I seek.
I am wondering whether a similar method would work for a function of two
variables.


texts: Solving recurrence relation with two recursive calls

texts:
I'm studying the worst case runtime of quicksort under the condition that it will never do a very unbalanced partition for varying definitions of very.

In order to do this I ask myself the question what the runtime $T(n, p)$ would be in the case quicksort always happens to partition in some fraction $0 < p \leq {1\over 2}$ such that $\lfloor{p(n-1)}\rfloor$ elements are in the left partition and $\lceil(1 - p)(n - 1)\rceil$ are in the right partition (leaving $1$ element, the pivot, in the middle).

It shouldn't be hard to see that $T(n, p)$ gives an upper bound for the worst case where $p$ is the maximally unbalanced allowed partition, as any partition with fraction $> p$ will be more balanced and have a smaller runtime, and any fraction $<p$ is not allowed.

It's obvious that $T(n, {1 \over 2})$ is the best case and $T(n, 0)$ is the worst case of quicksort. Both have easy recurrence relations that are found in any educational resource. But I have no clue how to study $T(n, p)$ in general. The obvious relation would be:

$$T(n, p) = n + T(\lfloor{p(n-1)}\rfloor, p) + T(\lceil(1 - p)(n - 1)\rceil, p)$$

Here I get stuck. I've tried searching around, but all literature that I could understand about divide and conquer algorithms took the "divide" literally and "cheated" the analysis using the fact that the partitions are always equal in size, merging the terms into one times a constant.

I do not know how to deal with two recursive calls, and I do not know if it is safe to remove the rounding. Is this possible to solve analytically, and if yes, how?

P.S.: I'm not interested in asymptotics (which is easy to show $\Theta(n \log n)$ for any constant $p$). I am interested in how much slower quicksort becomes as $p$ gets smaller, for example I'm interested in the ratio $T(n, 0.25) \over T(n, 0.5)$.

P.P.S: As an undergraduate student I apologize if I've made obvious things too lengthy or underexplained nontrivialities. And while I don't know if it's looked down upon here so much as other SE sites, I'll note that this is personal interest, not homework.


texts: Kolmogorov Complexity: Why would you need more bytes than the string itself?

texts:
I was reading Wikipedia's entry on Kolmogorov Complexity (thanks to this question), which states:

  It can be shown that the Kolmogorov complexity of any string cannot be more than a few bytes larger than the length of the string itself.

Why would you ever need anything more than the string itself to describe it?


texts: Why assume Turing machine can compute arbitrary results in Kraft-Chaitin theorem?

texts:
The Kraft-Chaitin theorem (aka KC theorem in Downey & Hirschfeldt, Machine Existence Theorem in Nies, or I2 in Chaitin's 1987 book) says, in part, that given a possibly infinite list of strings $s_i$, each paired with a desired program length $n_i$, there is a prefix-free Turing machine s.t. there is a program $p_i$ of length $n_i$ for producing each $s_i$, as long as $\sum_i 2^{-n_i} \leq 1$. The list of $\langle s_i, n_i \rangle$ pairs is required to be computable (D&H, Chaitin) or computably enumerable (Nies).

The proofs in the above textbooks work, it seems, by showing how to choose program strings of the desired lengths while preserving prefix-free-dom.  The details differ, but that construction is the main part of the proof in each case.  The proofs don't try to explain how to write a machine that can compute $s_i$ from $p_i$ (of course).

What I'm puzzled about is why we can assume that an infinite list of results can be computed from an infinite list of arbitrarily chosen program strings using a Turing machine that by definition has a finite number of internal states.  Of course many infinite sequences of results require only finite internal states; consider a machine that simply adds 1 to any input.  But in this case we're given a countably infinite list of arbitrary results and we match them to arbitrary (except for length and not sharing prefixes) inputs, and it's assumed that there's no need to argue that a Turing machine can always be constructed to perform each of those calculations.

(My guess is that the fact that the list of pairs is computable or c.e. has something to do with this, but I am not seeing how that implies an answer to my question.)


texts: Algorithm for factoring elements of permutation groups?

texts: You can solve a Rubik's cube by factoring its permutation into a sequence of "elementary" permutations (a subset of permutations that is sufficient to construct every other permutation in the group). There are several algorithms for solving Rubik's cubes. Are there any algorithms for the general problem of factoring permutations?


texts: Meaning of topological distance between 2 pixels

texts: I came across the notion of topology and topological distance in the context of image processing several times (especially when it came to mathematical morphology). I looked for a not too abstract explanation of "topological distance" but haven't found one yet. Can you please explain (in layaman's terms) the notion of topological distance between 2 pixels? And what's the difference between a euclidean distance and a topological distance in image-processing?


texts:
I had previously asked a question on space complexity of radix sort here. I have also read this question. However, I still get confused about it which means that the concept is not clear. I have the following implementation which is meant only for positive integers:

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <sstream>
#include <algorithm>

void radix_sort(std::vector<int>& arr)
{
    int rad = 1;
    int max_val = *(std::max_element(arr.begin(), arr.end()));
    while(max_val / rad)
    {
        std::array<std::vector<int>, 10> buckets;
        int n = arr.size();
        for(int i = 0; i < n; i++)
        {
            buckets[arr[i] / rad % 10].push_back(arr[i]);
        }

        auto k = arr.begin();
        for(auto b : buckets)
        {
            k = std::copy(b.begin(), b.end(), k);
        }

        rad *= 10;
    }
}

void print_array(std::vector<int>& arr)
{
    for(auto num : arr)
    {
        std::cout << num << "\t";
    }
    std::cout << "\n";
}

int main()
{
    int val;
    std::vector<int> arr;
    std::string s;
    std::cout << "Enter the numbers in the array: \n";
    std::getline(std::cin, s);
    std::istringstream ss{s};
    while(ss >> val)
    {
        if(val != ' ')
        {
            arr.push_back(val);
        }

    }
    std::cout << "Before sorting: \n";
    print_array(arr);
    radix_sort(arr);
    std::cout << "After sorting: \n";
    print_array(arr);
    return 0;
}

The time complexity is O(kn) and space complexity is O(k + n). Here n is the number of elements and k is the number of bits required to represent largest element in the array. My problem is with k and I am not able to understand how that effects the complexity. In the above code the number of times the outermost while loop runs depends on the number of digits of maximum value. Until recently I assumed that k represented this number of digits of maximum value. However, that is not the case. Can anyone please explain in simpler terms?

Edit: Pseudocode

1) Take the array as input

2) Initialize a variable `rad` as 1

3) Find maximum value element in the array

4) Until all the digits in maximum value element are visited:

          i) Create buckets for digits from 0 to 9.

          ii) Based on `rad`, calculate digits in a particular place of number (eg: unit's, ten's, hundred's etc.).

          iii) Fill the buckets with elements, based on the digit they have in the place under consideration in the loop.

          iv) Take out the numbers from buckets in the order bucket0 to bucket9 and use it to populate the original array.

          v) Update `rad` to change the place under consideration for the next loop.


texts:
I have a few questions regarding slotted-ALOHA. Assume a network have 25 users and transmission request probability = 0.25.

1) What is the throughput and what is the probability that a user will successfully transmit a frame after three unsuccessful attempts? I have managed to calculate the throughput as 0.00627. But the major problem is the probability to succeed after 3 attempts. Should I use these two formulas?

$$ n_a = \sum_{n=0}^\infty n(1-p_a)^n p_a $$

$$ n_a = \frac{1-p_a}{p_a} $$

2) What is the average number of unsuccessful attempts before a user can transmit a frame in the above problem?

Can somebody assist me?

Best regards


texts:
A set $\mathcal{A}$ is the relaxation of another set $\mathcal{B}$, if $\mathcal{B} \subseteq \mathcal{A}$.

I have a set of points defined as the knapsack constraint

$$
\mathcal{X} = \{x \in \mathcal{Z}^n: w^{\top}x \leq b \}
$$
where $\mathcal{Z}^n$ is the n-dimensional 0-1 vectors and $w \in \Re^n_+$ and $b \in \Re_+$.

I read that one possible relaxation of the above set is
$$
\mathcal{X} = \{x \in \mathcal{Z}^n: \lfloor w\rfloor ^{\top}x \leq \lfloor b\rfloor \}
$$

where $\lfloor \rfloor$ represents the floor function.

It is very counter-intuitive to me.  $w^\top x \leq b$ represents a half space with left or lower space of the hyperplane defined by $w^\top x = b$. By taking the floor function, we are in fact moving the hyperplane lower and shrinking the size of the set.

Can anyone explain to me why the floor function terms represent a relaxed set ?


texts: Difference between Bandwidth and Propagation Speed in computer networks?

texts: I want to know the difference between Bandwidth and propagation speed. How are they associated with each other i.e. the impact on bandwidth if propagation speed varies or the impact on speed if bandwidth varies. I have gone through this difference between propagation speed and bandwidth in digital communication still I am unable to understand it very clearly. Could it be possible to explain with some other example like may be with water pipes etc.


texts: Understanding Wirth's symbol table entry

texts:
N.Wirth's book on compiler introduces the concept of symbol table and states that
every declaration statement results in a new entry in symbol table.

Then after showing how an entry in symbol table looks like he talks about types which can be specified anonymously like the following :

$\ VAR a: ARRAY 10  OF INTEGER $

Then it is written that  named types are represented in the symbol table entry by an entry of type object -----(1)

which in turn refers to an  object of type "Type" and provides the following snippet :

$\ Type = POINTER TO TypDesc;
TypDesc = RECORD
 form, len: INTEGER;
 fields: Object;
 base: Type
END  $

The book is written in pascal or oberon and I don't understand its syntax but
I want to know how to interpret this type desc .

Does whatever follows typedesc , describes the fields of the record ? Form ,length,fields and base being the columns of the record ?

Wirth ,for the following declaration :

TYPE R = RECORD f, g: INTEGER END ;
VAR x: INTEGER;
 a: ARRAY 10 O OF INTEGER;
r, s: R;

shows the following symbol table entry :

The picture , I am getting from this is every object will point to its "type" ,.

In case of records , the type will point to the first field . I guess each field is being implemented something like a C structure ,having the pointer to the next field and pointer to its base type as its member . And here in the diagram ,the attribute "next" is pointing to "g" and its attribute "type" is pointing to "integer" .

The above was just an attempt to interpret what the author exactly means by it . Is my understanding correct ?


texts: Turing machine with an oracle for a proper subset of a known undecidable language

texts:
Consider a Turing machine $T$ with access to an oracle for a proper, nonempty subset of $A_{TM}$, say $L$. That is, $T$ can query this oracle to check whether some string belongs or doesn't belong to $L$. Is it possible to define such an $L$ so that $T$ does not decide $E_{TM}$ (the language of descriptions of Turing machines whose languages are empty)?

Intuitively, it seems the problem is that when the oracle answers "No", $T$ is unable to distinguish whether the string it fed to the oracle to receive this response belongs to $A_{TM} - L$ or $\overline{A_{TM}}$. But this doesn't really prove that $T$ can't decide $E_{TM}$.


texts: Recognize if graph has Hamiltonian cycle from subgraphs

texts:
There is a graph G, which is not known to me. Instead I am given the multiset of all graphs that are obtained by deleting a single vertex from G. My task is to figure out, from all of these subgraphs, whether the original graph G has a Hamiltonian cycle.

My original idea was to assert that, if all of these subgraphs have Hamiltonian paths, then G has a Hamiltonian cycle - but it was pointed out that my reasoning was flawed and this is not actually the case (for example, all such subgraphs of the Petersen graph have Hamiltonian paths, but the Petersen graph does not have a Hamiltonian cycle). And this is where I'm stuck. How could I get to the answer?

(full disclosure - this is a homework exercise)


texts: 3 dimensionnal matching to partition transformation

texts:
We want to transform $3DM$ to $PARTITION$, I am reading Garey and Johnson book and I really don't understand how they do the transformation, I know how they create elements $a_i$ from triples of set $M = W \times X \times Y$, but I don't know why they add two other elements $b_1$ and $b_2$ with definition
$$
s(b_1) = 2 (\sum_{i=1}^{k} s(a_i)) - B \\
s(b_2) = (\sum_{i=1}^{k} s(a_i)) + B
$$

with $B$ being:
$$
 B = \sum_{j = 0}^{3q - 1} 2 ^ { pj}
$$
and $p = [log_2(k)] + 1$ and $q$ is the number of elements in $X$ (Y, W also have the same number of elements) and also $k$ is the number of triples in $M$.

It would be very nice if anyone could clarify this transformation.


texts: Cutting equal sticks from different sticks

texts:
You have $n$ sticks of arbitrary lengths, not necessarily integral.

By cutting some sticks (one cut cuts one stick, but we can cut as often as we want), you want to get $k<n$ sticks such that:

All these $k$ sticks have the same length;
All $k$ sticks are at least as long as all other sticks.

Note that we obtain $n + C$ sticks after performing $C$ cuts.

What algorithm would you use such that the number of necessary cuts is minimal? And what is that number?

As an example, take $k=2$ and any $n\geq 2$. The following algorithm can be used:

Order the sticks by descending order of length such that $L_1\geq L_2 \geq \ldots \geq L_n$.
If $L_1\geq 2 L_2$ then cut stick #1 to two equal pieces. There are now two sticks of length $L_1 / 2$, which are at least as long as the remaining sticks $2 \ldots n$.
Otherwise ($L_1 < 2 L_2$), cut stick #1 to two unequal pieces of sizes $L_2$ and $L_1-L_2$. There are now two sticks of length $L_2$, which is longer than $L_1-L_2$ and the other sticks $3 \ldots n$.

In both cases, a single cut is sufficient.

I tried to generalize this to larger $k$, but there seem to be a lot of cases to consider. Can you find an elegant solution?


texts: how to prove correctness of this BFS algorithm?

texts:
Given an undirected connected graph, I wrote the following algorithm based on BFS. The algorithm detects wether this graph contains a cycle. If it contains a cycle then prints it. I'm pretty sure that it works just fine, but I don't really know how to prove its correctness properly.
Here is the pseudo-code:

Let s be the root
set parent[s]=s and parent[v]=null for all other v
create queue q ;
enqueue(s,q);
cycle=false;
while (!isEmpty(q) && !cycle) {
 u=front(q);
 for every edge (u,v) incident to u {
 if (parent[v]==null){
  parent[v]=u;
  enqueue(v);
 }
 else if (parent[u]!=v){
   cycle=true;
   keep the edge (u,v)
 }
dequeue(q);
if (cycle){
 print edge (u,v)
 while (parent[u]!=parent[v])&& (parent[v]!=u)&&(parent[u]!=v){
        print edge (u,parent[u]) and  edge (v,parent[v])
        u=parent[u];
        v=parent[v];
    }
    if (parent[u]==parent[v])
        print edge (u,parent[u]) and edge (v,parent[v])
    else
        print edge (u,v)
}
/**************************************************/
/**************************************************/

I've been working on the proof but i can't get through it.
 First i want to prove that if G contains a cycle then the algorithm does detect it.
My idea is the following:
Let s be the root of the bfs. We know that G contains a cycle, so there is a node such that there are two different paths from s to such a node. Let u be the first node that satisfies this.
Since that BFS visits all the nodes, and  explores each edge once, and also marks as visited all nodes that were visited, it will reach a step in which it is about to visit  the node u for the second time and then it finds the cycle.

Then I want to prove that in the afirmative case, the edges that it prints does forms a cycle, but i'm really stuck with this.


texts:
Say I have:

page size = 2^12 bytes
physical memory = 2^24 bytes
logical address space = 2^32

How many page-table entries are needed in case the program uses the whole logical address space?


texts: Examples for CFG that cannot be expressed by regular language

texts:
There are nice examples for context free grammars which cannot be expressed with regular language, for example the palindrome and a similar contrived example here, but they are very intuitively applicable for formal languages, e.g. checking for balanced nested parentheses and such.

Can you conceive an example that is pertinent to natural languages?

Part of the motivation to this question is that in one view, regular expressions are practically intractable when it comes to combining and scaling them to describe natural language phenomena; they don't compose as nicely as grammars. But at the same time I can't easily think of an actual example where regular expressions should not be enough for describing natural languages.

An example, therefore, for some natural language phenomena that cannot be modelled with regular language, would be very nice and interesting!


texts: Why use maximum likelihood for word prediction?

texts:
According to https://www.tensorflow.org/tutorials/word2vec/, the standard approach for predicting the next word in a word sequence is maximum likelihood. The predicted next word is the word that maximizes

$$P(w_t|h)=\frac{\exp(\text{score}(w_t,h))}{\sum_{w'}\exp(\text{score}(w',h))}.$$

To me, it seems that the word predicted from this model is always the word with the maximum score, in which case we could just use the score function for prediction.

What does maximum likelihood provide that a simple score function does not?


texts: Proving a Greedy Algorithm is Incorrect by Providing Counter Example and Coming up with another correct algorithm

texts:
I want to come up with a counter example that proves the following greedy algorithm doesn't work and give an alternative correct algorithm. The problem is I have an array of numbers and I want to reach the last element of the array in the minimum number of steps. At each step, I can move to any element with the same value, move forward one, or move backward one. The greedy criterion is to move furthest to the right as much as possible. For example, if we have array {1,2,3,4,1,5}, the algorithm will start at 1 move to 1 before the 5 then moves to 5 with number of steps of 2.

An an example of input instance that proves the given greedy algorithm wrong might be {1,2,1,3,2} where the given algorithm crosses the array in 3 steps whereas there is an optimal solution of moving from 1 to the second 2 right to last 2 in two steps. Now, what is a correct algorithm for solving this problem ?


texts: Dijkstra's Notes on Structured Programming - concerning the program to compute first 1000 prime numbers

texts:
In his "Notes on Structured Programming" essay, E. W. Dijkstra gives an example of a program that computes the first 1000 primes (Section 9. "A First Example of Step-Wise Program Composition").

The idea is to iterate all the numbers from 1 to 1000 in increasing order, to test each one and if found to be prime save it into an array p. The test consists of giving an answer to the question of whether the number j is divided by one of the primes found earlier: if it is divided - the number is not prime; otherwise - it is prime.

j is the number under test and here it is assumed to be incremented by 1 at each iteration (in the original paper an optimization has been introduced where j is odd and incremented by 2).
The smallest array index is 1.

Next is an excerpt from the paper followed by the question proper:

  We use the facts that
  (1) [...] the smallest potential factor to be tried is p[1]
  (2) the largest prime number to be tried is p[ord - 1] where p[ord] is the smallest prime number whose square exceeds j.

  (Here I have also used the fact that the smallest prime number whose square exceeds j can already be found in the table p. In all humility I quote Don Knuth's comment on an earlier version of this program, where I took this fact for granted:
  "Here you are guilty of a serious omission! Your program makes use of a deep result of number theory, namely that if $p_n$ denotes the $n$-th prime number, we always have
  $$
p_{n+1} < (p_{n})^2
$$
  " Peccavi.)

In my analysis I have arrived at the conclusion that the program does not depend on this result; that is - the program will work correctly even if the inequality above were not true.
Help is needed in finding the error in my line of reasoning, or to identify the misunderstanding of the source material, if that were the case.

The program makes use of a lemma

  If a natural number $n > 1$ is composite, then $n$ is divisible by some prime number $p \leq \sqrt{n}$.

(A proof can be found in "Discrete Mathematics" 2nd ed., by Edgar G. Goodaire, page 116)

Thus when we test number j for primality we only need to consider those primes whose squares are less than or equal to j.

Suppose that we have computed the first $n > 1$ primes and all of them are in the array p. We next initiate the process of computing the next prime $p_{n+1}$ by incrementing j and testing it for primality.
In the case where $p_{n} < j < (p_{n})^2$, there exists a prime $p_{k}$ such that $$(p_{k-1})^2 \leq j < (p_{k})^2$$
The potential factors of j are $p_{1},p_{2},..,p_{k-1}$ and all of them are in the array p, thus if the next prime lies in the interval $p_{n} < j < (p_{n})^2$ we are guaranteed to find it.
This is the case which corresponds to the theorem pointed by Don Knuth, and since we know it to be true, we could stop here as far as program correctness is concerned.

But for the sake of argument, let's continue and consider the case $j > (p_{n})^2$. All of the numbers $p_{n} < i < j$ are composite, so the largest prime less than j is $p_{n}$ and, by our assumption $(p_{n})^2 < j$. Thus the potential factors of j are $p_{1},p_{2},..,p_{n}$ and all of them are in the array p.

Given that in both cases the entire list of primes whose square is less than or equal to j is in the table p, and that's the necessary and sufficient condition for the primality test, we conclude that the relation $p_{n+1} < (p_{n})^2$ plays no role in the operation of the program.


texts: Algorithm to compute string prefix similarity

texts:
Given a string, how to get the its prefix similarity? I use an example to explain what I mean by string prefix similarity. Say, s = "ababaa". We take all its suffixes, that is, "ababaa", "babaa", "abaa", "baa", "aa", "a". Then we count their common prefix length with original string. In this case, it is 6 + 0 + 3 + 0 + 1 + 1 = 11.

I hope my question is clear. The straightforward method has complexity $O(n^2)$. Can we do better?


texts: Higher order empirical entropy is not the entropy of the empirical distribution?

texts:
Basically, the problem is that I always thought that the (unnormalized) $k$th order empirical entropy $n\cdot H_k(x)$ (see "Backround" at the end of this post for more information) for a given string $x$ of length $n$ equals the entropy of the empirical distribution on the set of all words of length $n$ (the conditional probabilities are taken from the observed occurrences in $x$). Until today, I was totally sure that this is true, but it seems to be wrong for very easy examples (e.g. for $x=1011$).

To be more accurate, consider $\Sigma=\{0,1\}$, $x=1011$ and $k=1$ such that $$n\cdot H_k(x)=4\cdot H_1(x)=2.$$
On the other hand, the corresponding empirical distribution is a First-order Markov source described by

$P(\text{The first letter is }0)=0$
$P(\text{The first letter is }1)=1$
$P(\text{Letter }0 \text{ immediately follows after letter }0)=0$
$P(\text{Letter }1 \text{ immediately follows after letter }0)=1$
$P(\text{Letter }0 \text{ immediately follows after letter }1)=0.5$
$P(\text{Letter }1 \text{ immediately follows after letter }1)=0.5$

Now this probabilities yield a random variable $X$ on words of length $n=4$, where the Shannon entropy is
$$H(X)=-\sum_{w\in\Sigma^4}P(w)\log P(w)=\frac{9}{4}.$$
(You only need to consider words of length $4$ which start with $1$ and do not contain $00$.)

But shouldn't be both measures intuitively give the same value?
I did the calculations more than once, so I am pretty sure the mistake is in my understanding, not in the calculation.
Or did I always thought something wrong? But it seems so clear that the empirical entropy is the entropy of the empirical distribution (also for higher order Markov sources).

$ $

$ $
Backround
For a given string $x\in\Sigma^n$ over an alphabet of size $k$, the ($0$-th order) empirical entropy is defined as
$$H_0(x)=\frac{1}{n}\sum_{i=1}^{k}n_i\cdot\log \frac{n}{n_i},$$
where $n_i$ is the number of occurrences of the $i$th alphabet symbol.
The $k$-order empirical entropy ($k\ge 1$) is then defined as
$$H_k(x)=\frac{1}{n}\sum_{|w|=k}|S_w|H_0(S_w),$$
where $S_w$ is the string obtained by concatenating the characters immediately following occurrences of $w$ in $x$.


texts: What techniques could be used to support thread-local contexts and resources in a language?

texts:
I am interested in the subject of thread-local contexts, which is a feature that I use quite often in solutions, but seems to lack first-class support in any languages I have used.

Quite often in programming - especially if you are implementing a solution that repeatedly processes similar inputs - it is useful to have access to a thread-local context.

I am sure many are familiar with this problem: the typical case I am taking about is where you have a processing engine taking input messages/requests (e.g., an MDB or a Servlet in Java) that is instantiated individually for several threads, and this engine repeatedly processes the messages using some resources or context that it owns. These resources could be expensive to recreate (and therefore we would like to reuse them), or alternatively, they need to be retained across requests in the thread, but do not need global scope in the application.

In this case, code needs to be able to access that context in an efficient way, but due to the stack+heap-based approach of most languages this is difficult. The current solutions are to either use something like ThreadLocal in Java or to pass a pointer to the context down the stack, both which are not really language constructs, and both of which impose some overhead (and in the second case have practical issues).

It occurs to me that such a thread context is a bit like a second stack. A stack has thread scope and can be efficiently accessed by the thread.

Possibly solutions to implement this in-language might be to maintain the context at the base of the stack; however, this would have to be a fixed size. For a variable sized context, a reference could be stored at the base, but with some loss of efficiency for minimalist requirements. Other options might be possible if the hardware supported multiple stacks per thread.

As a trivial example of what I mean to illustrate the performance impact of existing solutions would be to imagine each "engine" receives a message and then increments a counter (counting the number of messages processed per for each thread). Using ThreadLocal would be many times less efficient that simply incrementing the contents of a known memory address. Even a global counter would require some synchronization and therefore would create a choke point.

A more practical example would be the maintenance of a resource pool such as an object pool where expensive-to-create objects or buffers can be re-used across invocations.

To be clear: this is not really a multi-threading issue, so solutions such as semaphores, etc. are not the solution - on the contrary, they are part of the problem.

A thread-local resource does not need to be shared between threads. It is local, so any solution adding the overhead of synchronization is adding an unnecessary performance penalty.

It would be interesting to know how this might be done (or if it has been done already), with particular consideration to the hardware support available to make it efficient.


texts: Why aren’t (type theory based) automated theorem provers efficient?

texts:
Note: my main experience with theorem provers is with Type theory based proof-assistant, rather than an actual automated theorem prover.

It is obvious why naive automated theorem proving is inefficient: just doing an uninformed search through proof-space (e.g. with breadth first search) runs into the problem that the number of nodes in the proof tree increases exponentially with the number of steps.

What I am wondering is: Why haven’t we yet been able to create heuristics that guide an informed search to the point that automated theorem provers beat human mathematicians in proving theorems across the board? What makes it difficult to formulate such heuristics?


texts:
We have the problem $C = \{<G,S>| \text{ S is a minimal cover of G }\}$ and we want to show that $C\in coNP$.

I can easily show that there's a ND TM that decides $coC$ using a guess to check if the drawn vertices are a minimal cover and if they are, return false. But it seems like it's wrong since this can be done with anything.

So is there another way to show that?


texts: What is the proper runtime for visiting all outgoing edges in an adjacency list?

texts:
Suppose that we have a directed graph $G = (V, E)$ represented as an adjacency list.  Suppose that we want to list all of the edges incident to some node $v \in V$.  We can do this by iterating over all the elements in the adjacency list.

My question concerns the runtime of this operation.  Is it proper to say that the runtime is $\Theta(deg^+(v))$ (since the runtime is a linear function of the outdegree of $v$)?  Or should it be $\Theta(1 + deg^+(v))$, since even if $deg^+(v)$ is zero, there is some amount of work that's still done?  Or are both of these terminologies incorrect because there is no underlying variable $n$ for which we could apply the formal definition of $\Theta$?

Thanks!


texts:
Is "flops" a reliable measure of deciding computational capacity? If we do matrix multiplication and matrix addition of the same size of matrix, do the flops remain the same?

Referring to question https://stackoverflow.com/questions/329174/what-is-flop-s-and-is-it-a-good-measure-of-performance

I am curious to know if I do a 100x100 matrix multiplication and matrix addition, will the FLOPS remain the same? Can I say time required by the processor (and hence FLOPS) remain same regardless of operation?

Can someone also comment on how theoretical maximum FLOPS of a processor are determined. And if FLOPS is taken as standard measure of performance, then can someone use an algorithm that will always be highly efficient but not useful in scientific computing?


texts: Is the runtime for the general number sieve given in base 10, e or 2?

texts:
When the runtime of the GNFS is given as e^(64/9*b(log b)^2)^1/3,
what base is the log?  I'm assuming its e, but other options would obviously be 10 and 2.


texts:
I am trying to fully understand the meaning behind the self-information of events. While I totally understood how to calculate it, all explanations I find online lack of an explanation why less likely events have more self-information.

I can't figure out what consequences this has and can't put it into perspective like other concepts in computer science.

What does the self-information really mean? Can someone put it into context and why exactly less likely events have a higher self-information?


texts: What resources are there for students to compute on a data stream?

texts: I teach a randomized algorithms course, and many of the cool applications are to streaming computation. I can have students implement these algorithms in Python or C++, but I feel it would be much cooler to have them do it in a streaming environment. Unfortunately, as far as I can tell, IBM Streams and Google's BigQuery are prohibitively expensive. Are there free tools for educational use? You would think that companies would want students to learn these things in college, rather than constantly having to train them on the job.


texts: Approximation algorithm for the partition problem

texts:
In the partition problem we want to partition a set $S$ of positive integers into two sets $S_{1}$ and $S_{2}$ such that the sum of the integers in the two sets is the same.

The optimization version of the problem is NP-Hard, in the following wikipedia page an 7/6 approximation algorithm is described. In that algorithm, we sort the original set $S$, traverse the new sorted set in descending order and send each element to the set $S_{i}, i\in\{1,2\}$ that has the minimum total sum at the given moment.

My question is, does the traversal have to be in descending order? If we do it in ascending, does anything change in the final approximation ratio?


texts: State of art quadratic knacksack algorithms

texts: What is the current status to quadratic knacksack problem? Say, how many variables can the state of art solver handle? Thank you.


texts: What is the purpose of M:N (Hybrid) threading?

texts:
In other words, what advantages does Hybrid threading have over 1:1 (kernel only) and N:1 (user only) threading?

This is a follow-up to What is the difference between user-level threads and kernel-level threads?


texts: How can a quadratic algorithm be faster than a linearithmic one?

texts:
I have to solve the following problem:

  Al and Bob are arguing about their algorithms. Al claims his $O(n\log n)$ time method is always faster than Bob’s $O(n^2)$ time method. To settle the issue, they perform a set of experiments. To Al’s dismay, they find that if $n<100$, the $O(n^2)$ time algorithm runs faster, and only when $n \geq 100$ is the $O(n\log n)$ time one better. Explain how this is possible.

Watching the Big O definition I can see that $f(x)$ is $O(g(x))$ if there are constants $C$ and $k$ such that $|f(x)|\leq C|g(x)|$ whenever $x>k$.
Also, I know that $O(n^2)$ comes from a polynomial of degree 2 that might have a coefficient and other terms of lower degree.

I do not find how to relate this facts in order to make a conclusion although I suspect that constants $C$ and $k$ could play an important role in such a conclusion.

I will very much appreciate any clue so I can get a better idea about how to formulate an answer.


texts: Basic queries for Object Detection using deep learning

texts:
I have recently started working on the Object detection using deep learning.

I have understood the basic steps of object detection are:

Input Image -> Object proposals -> Feature Extraction -> Training.

I have successfully implemented my own code up to the Object Proposal extraction. Now I want to use deep learning here from that point. For the input to deep learning I have fixed number of object proposals (i.e. 800 proposals from one image) and I need a labeled data.
For example:
I have a one class dataset. 1) Aircraft,
Images number 1-90 are aircraft.
and the above number of images have 800 aircraft.
Q: Here, I want to ask that how can I make the labels for the dataset with this configuration of class? According to the tutorials and the Matlab implemented examples I have seen, they used the images and the training labels as the input to the CNN. As I have training images I want to know how can i make training labels.

The input to the CNN network will be proposals (just a cropped regions) around 500 proposals. I want the output is to be if any of the proposals is matched as aircraft then it will appear a bounding box on the big image that this is a aircraft.

Input image.


texts: How to calcualte the Big-O complexity of the following algorithm?

texts:
I have been trying to calculate the Big-O of the following algorithm and it is coming out to be O(n^5) for me. I don't know what the correct answer is but most of my colleagues are getting O(n^3).
for(i=1;i<=n;i++)
{
    for(j=1 ; j <= i*i ; j++)
    {
        for(k=1 ; k<= n/2 ; k++)
        {
        x = y + z;
        }
     }
}

What I did was start from the innermost loop. So I calculated that the innermost loop will run n/2 times, then I went to the second nested for loop which will run i^2 times and from the outermost loop will run i times as i varies from 1 to n. This would mean that the second nested for loop will run a total of Sigma(i^2) from i=1 to i=n so a total of n*(n+1)*(2n+1)/6 times. So the total amount that the code would run came out to be in the order of n^5 so I concluded that the order must be O(n^5). Is there something wrong with this approach and the answer that I calculated?
I have just started with DSA and this was my first assignment so apologies for any basic mistakes that I might have made.


texts: If O(log n) vs O(n) is exponential what is O(1) vs O(n)?

texts:
If one refers to using an O(log n) instead of an O(n) algorithm as an exponential speedup,
how would one refer the speedup gained by using an O(1) algorithm vs an O(n)?


texts:
I'm looking for an algorithm that provides a canonical string for a given colored graph. Ie. an algorithm that returns a string for a graph, such that two graphs get the same string if and only if they are isomorphic.

In particular, I'm looking for a simple algorithm that is easy to implement with a reasonable performance on most graphs (worst case super-polynomial, of course). I'm expecting small graphs, so performance doesn't have to be stellar, just good enough.

Unfortunately, most things I've found are highly complex and more interested in expressing deep mathematical connections than simply describing the algorithm. I'm afraid I don't have the time to dive that deep. Can anyone give me a shortcut?

I'm hoping for something like the Floyd-Warshall algorithm. Not optimal, but good enough, and easy to implement.


texts: Corner cases in the Interleave Lower Bound for BSTs

texts:
The Interleave lower bound is a lower bound for the amount of operations any Binary Search Tree needs to make for a sequence of accesses. It is used in the construction of Tango Trees, and is based on Wilber's lower bound.
The Interleave lower bound is proved by defining a Transition Point for every node $y$ in a static tree $P$.
See Demaine, Erik D., et al. "Dynamic optimality-almost." SIAM Journal on Computing 37.1 (2007): 240-251: Section 2 and Appendix A.

I see a problem with the definedness of the transition point for nodes in the tree that don't have a right subtree, such as leaves, for which there doesn't exist a path from the root that contains both elements from the left subtree + $y$ and from the right subtree of $y$.

Does it constitute a problem to the analysis of the bound?
It certainly seems to weaken Lemma A.1. For any node y in P and any time i, there is a unique transition point for y at time i.
If we consider the transition point of such nodes in $P$ to be themselves in $T_i$ then there is a problem with Lemma A.3. At any time i, no node in T_i is the transition point for multiple nodes in P.

Can the analysis and the bound be kept by not counting the interleaving through the leaves (and possibly their parents), and thus avoiding the need to refer to their transition points?


texts: What happens to uninterpreted predicates in Ackermann's reduction?

texts:
I know the procedure to apply the Ackermann's reduction to a formula that doesn't involve uninterpreted predicates. But, how do we treat the uninterpreted boolean predicates? Nearly all the examples I have seen, usually just assume there are no uninterpreted predicates, and give examples of simpler reductions, but if we have something like this:

$$p(z, F(x_1)) \wedge F(F(x_1)) = G(x_2,G(x_1,x_3,x_4),F(x_2)) \rightarrow p(x_1,y)$$

How will I get rid of the uninterpreted predicate, so that I can apply the usual reduction?


texts: Algorithm to create n arrays with maximum difference

texts:
Let's suppose I want to generate n equal sized boolean arrays with maximum "difference". - "Difference" in this case is defined as that the arrays share as low as possible fields with one another. (an example of share: array1 = {1,0,0,0) and array2 = {1,1,1,1} -> array1 and array2 share 1 field (array1[0] / array2[0])

Just for example: n would equal 2 and the size of the field would be 6
-> the optimum solution would be the arrays [0,0,0,0,0,0],[1,1,1,1,1,1] because they share no fields and so are very "different" from one another
Another example: n was equal to 4 and the size of the array would be 4
-> a solution would be [0,0,0,0], [1,1,1,1], [1,1,0,0], [0,0,1,1] - the arrays share 1.33 fields per array by average

Has anybody an idea of an algorithm or solution strategy that could solve this problem (generate n of these arrays) perfectly (or very good - so that they are as different as possible) (in a realistic runtime)? Thanks very much in advance :D


texts: Amplifying the correctness of $\mathsf{RP}$ algorithms using expander graphs

texts:
A graph $G = (V, E)$ is called an $(n, d, \varepsilon)$-expander if the graph has $n$ vertices, maximum degree $d$, and satisfies the following expansion property:

for every subset $W\subset V$ such that $|W|\leq n/2$, $|W\cup N(W)|\ge (1+\varepsilon)|W|$

where $N(W)$ is the neighborhood of $W$ in $G$.  The expansion property means, informally, that the neighborhood of $W$ is "large" when $W$ is "small".  That expanders exist can be shown with the probabilistic method (see, e.g., this writeup from Ellis).

I'm trying to show that expanders can be used to amplify the success probability of one-sided Monte Carlo algorithms.  In particular, given a polynomial time algorithm $A$ for a problem in RP that uses $n$ random bits and gives false negatives with probability at most $1/2$ we want to show there is a polynomial time algorithm that uses $n$ random bits and gives false negatives with probability at most $n^{-c}$ for a fixed constant $c$.

Here is the method I've been asked to analyze.  We regard $A$ as a function $A(x,r)$ where $x$ is the input and $r$ is a string representing the random bits.  On the input $x$ we then:

Fix a $(2^n,d,\varepsilon)$-expander $G$ and identify its vertices with $\{0,1\}^n$
Select a vertex $r$ of $G$ uniformly at random
Compute the set $y_1,y_2,\ldots, y_t$ of vertices at distance at most $\delta$ from $r$ in $G$
Say "no" if and only if $A(x,r),A(x,y_1), \ldots, A(x,y_t)$ are all "no"

What I need to show is that for $\delta = O(\log n)$ the probability of a false negative is at most $n^{-c}$.

As a side note, this is actually enough to accomplish the original goal.  A result of Gabber and Galil is that there is a family of $(2^n, 5,(2 - \sqrt{3})/4)$-expanders with the additional property that the neighbors of any vertex can be enumerated in polynomial time.  This means that $d$ and $\varepsilon$ can be taken uniformly in $n$, and that we can implement BFS from $r$ in polynomial time per vertex considered. Since $t\le d^{\delta + 1}$, the new algorithm runs $A$ a number of times polynomial in $n$ for $\delta = O(\log n)$ and $n$ is polynomial in the input size.  Since $G$ is deterministic and does not depend on $A$, there is also clearly no new randomness.

Here is how I approached the problem thus far.

Let $G$ be given. Since $|V| = 2^n$, we have an identification $V \cong \{0,1\}^n$. Let $r \in \{0,1\}^n$ be chosen at random so that $r$ corresponds to a random starting point in $G$. Define a ball $B(v,\delta) = \{u \in V: d(u,v) \leq \delta\}$ where $d(u,v)$ is the length of the shortest $uv$-path. We are only interested in the number of bad balls, namely balls such that all $u\in B(v,\delta)$ result in false negatives, that is, our $\mathsf{RP}$ algorithm should accept but reject nonetheless. If we can bound above the number of bad balls by $2^n/n^c$ for some constant $c$, then we are done since an error occur if and only if the chosen vertex $y_i$ is such that $B(y_i,\delta)$ is bad.

I tried bounding the number of vertices in a bad ball using the expansion property of $G$, but I am not sure how this could help considering balls are certainly not disjoint. We also know that at most $1/2$ of the vertices will result in a false negative.

Any help would be greatly appreciated.


texts:
What is the time complexity of computing $\frac{1}{2^n} {{n}\choose{(n+2)/2}}$?

$$\frac{1}{2^n} {{n}\choose{(n+2)/2}} = \frac{1}{2^n} \frac{n(n-1)\cdots ((n-2)/2)}{((n+2)/2) (n/2) \cdots 1}$$

The numerator and denominator in $\frac{n(n-1)\cdots ((n-2)/2)}{((n+2)/2) (n/2) \cdots 1}$ will take $O(n)$ multiplications.

$2^n$ will take $n$ multiplications.

So in total, there will be $O(n)$ multiplications. Is it the correct time complexity?


texts: Confusion about reduction of $L=\{w_i | M_i\text{ halts on }w_i\}$ to Halting Problem or Diagonalization language?

texts:
I want to reduce $L$ (stated above) to the Halting Problem in order to say that L is recursively enumerable but not recursive just like the Halting Problem, but is it enough to say that if I can solve the Halting Problem then I can solve $L$, because then I can feed into the Halting Problem the input $w_i$ twice, as both input and Turing machine encoding?

Do I need to reduce it to the diagonalization language instead?


texts: What do you call a lower/upper bound that is the best one?

texts: I have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound? If it were an optimization problem then I would call it the optimal value or the optimal bound. Is that right?


texts: Finding a fixed-size set whose members are contained by the largest number of other sets

texts:
I've been thinking about a problem, inspired by meeting a beginner-level foreign language professor at the Goethe-Institut who learned the five most common languages spoken by students in order to communicate with as many students as possible.

Consider some finite population of people, each of whom speak any number of languages. For the purposes of the problem, we'll ignore some of the things that make languages complex in real life (for example, that people speak several languages but at different levels, that people who understand one language might be able to understand closely-related languages, and so forth).

So, for example:

P1 speaks {English, German}.
P2 speaks {Spanish, Italian, French}.
P3 speaks {Mandarin, English}.
P10000 speaks {Afrikaans, Swahili, English}, and so forth.

I am writing some document which I wish to have translated so as to be understood by as many people as possible. Unfortunately, my budget is limited, and I can only afford a translation into N different languages.

For a given value of N, how do I calculate the optimimum set of N languages to reach the largest number of people out of the intended population?

The problem sounds like it could be easily generalized as a set-theory/combinatorics problem, and so I'm certain somebody has done work on something like it before. I would like to take a look at the existing literature, but I don't know how to find it.

Is there a name for this type of problem? If not, could it be reduced to another known problem?


texts: Proving that a certain language is regular using pumping lemma

texts:
Let $\Sigma = \{a,b,c,\ldots,x,y,z\}$ be the Latin alphabet, consisting of 26 letters. Consider the language $L$ of all words $\alpha$ over $\Sigma$ satisfying the following constraints:

If $\alpha$ contains $a$ then it contains exactly $4$ many $a$s.
If $\alpha$ contains $b$ then it contains exactly $8$ many $b$s.
...
If $\alpha$ contains $`$ then it contains exactly $2^{27}$ many $z$s.

How do I prove that $L$ is regular?
Note: I did research and I have found that we can use the pumping lemma.


texts: Finding vertices of a maximum clique in polynomial time

texts:
Say you were given a black box that solves a clique problem in constant time.

You give the black box an undirected graph G with a bound k and it outputs either "Yes" or "No" that the graph G has a clique with at least k vertices.

How would you use this black box to find the vertices of a maximum clique in polynomial time?


texts:
given a turing machine M over the input alphabet $\Sigma $ , any state q of M and a word w $\epsilon\Sigma $* , does the computation of M on w visit the state q ?

Is this problem decidable ?


texts: Decidability of empty intersection of two languages accepted by Turing machines

texts:
I am really struggling with determining the decidability of languages and cant figure out whether this problem is decidable or not.

I have a language

$\qquad\displaystyle
  L = \{ (R(M_1), R(M_2)) \mid L(M_1) \cap L(M_2) = \emptyset \}$,

where $R(M_1)$ and $R(M_2)$ are representations of Turing machines $M_1$, resp $M_2$ and $L(M_1)$, $L(M_2)$ are the languages accepted by these machines.

Is language $L$ a decidable language?

I have found this theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection. (but I dont know whether $L(M_1)$ and $L(M_2)$ are context-free, I only know that they are accepted by some machines, so I dont know if I can use this theorem).

I think that this problem is undecidable and my attempt to prove this would go like this:

In order for this language to be decidable. I would have to build a Turing machine that tests whether an arbitrary word is accepted by $M_1$ and not $M_2$ (and vice versa) but I cannot guarantee that it will halt for all inputs (since language acceptence does not guarantee that the language is decidable) so it proves the undecidability.

Is this correct approach?

Is $L$ at least recursively enumarable?


texts: Why is the Turing machine rather than the finite automaton the main model for computation if computers have finite memory?

texts:
Any physical computational device clearly has finite memory. On the other hand the input can be external and could therefore potentially be infinite. This idea is perfectly captured by the deterministic finite automata (DFA), so why do we use the Turing machines instead?
Let's consider a popular example. The language
$$L = \{a^nb^n, n\in \mathbb{N} \} $$
is recognizable by a Turing machine, but not by a DFA. Suppose that you are getting a string from a server, and you need to determine whether it belongs to $L$ or not. I'd say you can't do it, because you might, in fact, run out of memory.


texts: Do undecidable problems have no HO query? If so, could I have an example?

texts:
In descriptive complexity, HO corresponds to ELEMENTARY.

ELEMENTARY is a subset of R, so therefore all HO queries are decidable.

Then undecidable problems have no corresponding HO query.  Is my understanding correct?  If so, can I have an example undecidable problem and an intuitive/informal explanation of why it doesn't have a corresponding HO query?


texts: The notion of PAC in approximation algorithms

texts:
In computational machine learning, the notion of Probably Approximately Correct means that (generally speaking) we can find (or "learn") with a high probability a function which has "low error".
Is there a way to generalize this idea for approximation algorithms? What I thought of:
Given a language $L \subseteq \{0,1\}^*$, a confidence parameter $\delta\in[0,1]$, an error parameter $\epsilon > 0$, and a distribution $D$ over $L$, the algorithm $A$ is a PAC algorithm for $L$ if with probability at least 1 - $\delta$ it holds that $\text{ERR}(A,D)\leq \epsilon$, where $\text{ERR}(A,D) := \Pr_{x\text{~}D}(A \text{ answers wrong on } x)$.
One drawback of this definition is the following: suppose $L$ is a countable infinite set, and let $l_1, l_2,...,l_k,...$ be some enumeration of the elements of $L$. Since $D$ is a probability distribution over $L$, $\sum_{i}D(l_i) = 1$, and hence there must be some index $k$ such that $\sum_{j>k} D(l_j) <\epsilon$.
The algorithm $A$ can be defined as: remember the answers of the first $k$ words. When receiving $w \in \{0,1\}^*$ check if $w$ is saved (and if so answer correctly). Otherwise, answer "0".
Clearly this algorithm is a PAC by the above definition, but not a clever one.
Is there a way to define PAC algorithm for a formal language? Or: can we use the theory of machine learning in the theory of approximation algorithms?


texts: Communication complexity of comparing sets, for Bitcoin

texts:
In Bitcoin, when one node wants to tell another node about a block, it sends the block header, then all the transactions it contains. This is inefficient, because the receiving node might already have some or all of those transactions.

The sending node needs to tell the receiving node

the transactions that the receiving node does not have
which transactions are in the block
what order those transactions are in

What would be more efficient than sending all of the transactions? (Each transaction is about 160 bytes)

You could send a list of hashes of the transactions. That would reduce the overhead for each transaction to 20 bytes (if you used SHA1). The receiving node could ask for the transactions that it was missing. This is the most efficient method that I can think of - but I think there’s probably something better.


texts: Can I change the input of my reductionduring the proof?

texts:
To prove that a problem $\Pi_2$ is NP-hard one has to:

select a known NP-hard problem $\Pi_1$;
from an arbitrary instance of $\Pi_1$, create an instance of $\Pi_2$ in polynomial-time; and
show that solve $\Pi_1$ with the given instance $\iff$ solve $\Pi_2$ with the created instance.

Now, my question is the following.

Suppose now I did 1., 2. and only solve $\Pi_1\Rightarrow$ solve $\Pi_2$ but when I am trying to show the inverse, i.e., solve $\Pi_2\Rightarrow$ solve $\Pi_1$, the instance of $\Pi_1$ is changed a little. Is this proof correct?

More precisely, let $I_1=(n, a_1,\ldots,a_n,b_1,\ldots,b_n,\alpha,\beta,k)$  be an arbitrary instance of $\Pi_1$. The created instance (in polynomial-time) of $\Pi_2$ is $I_2=(n, a_1,\ldots,a_n,b_1,\ldots,b_n,\Delta,k)$. Now when I tried to show solve $\Pi_2$ with $I_2\Rightarrow$ solve $\Pi_1$ with $I_1$, I found another instance of $\Pi_1$, $I_1'=(n, a_1,\ldots,a_n,b_1,\ldots,b_n,a,b,k)$ where $a\neq \alpha$ and $b\neq\beta$. Hence I did not solve $\Pi_1$ with $I_1$ but with $I_1'$.

My guess is that the proof still correct, right?


texts: What Are the Ideas Behind Variations of the Coin Change Problem?

texts:
Problem: given a set of n coins of unique face values, and a value
  change, find number of ways of making change for change.

Assuming we can use a denomination more than once, here's the pseudocode I came up with

1. NUM-WAYS(denom[], n, change)
2.   dp = [change + 1][n + 1]
3.   for i = 0 to n
4      dp[i][0] = 1
5.   xs = denom.sorted

6.   for i = 1 to change
7.     for j = 1 to n
8.       if xs[j - 1] > i
9.         dp[i][j] = dp[i][j - 1]
10.      else
11.        dp[i][j] = dp[i - xs[j - 1]][j] + dp[i][j - 1]

12.  return dp[change][n]

The above algorithm is clear to me. However, if we are only allowed to use a denomination once, then line 11 changes to dp[i - xs[j - 1]][j - 1] + dp[i][j - 1], as if we are not allowed to use the current denomination at all. I'm failing to wrap my head around this. Can you explain this?

Here're some test runs:

Change: 3, denominations: [8, 3, 1, 2]
11111
01111
01222
01233

// use once
Change: 3, denominations: [8, 3, 1, 2]
11111
01111
00111
00122

Change: 4, denominations: [3, 1, 2]
1111
0111
0122
0123
0134

// use once
Change: 4, denominations: [3, 1, 2]
1111
0111
0011
0012
0001


texts: Does Turing Completeness imply the existence of a Universal Program?

texts:
Please correct me if at any time my definitions are wrong.
Suppose we have a programming language $L$ over some set $D$ with semantic (partial) n-ary functions $\varphi^n:D \to (D^n \to D)$. Assume $L \subseteq D$ (so programs are data as well).

We say that $L$ is turing complete if a function $f:D^n\to D$ is Turing Computable if and only if there exists a program $p \in L$ such that $f = \varphi^n(p)$.
We know there exists a universal Turing Machine: A Turing Computable function $U:D^2 \to D$ such that for every (encoding of) a Turing Computable function $T$, every $d \in D$: $U(T,d) = T(d)$.
Does this imply, via Turing Completeness, that there must be a universal program in $L$? Why or why not?


texts:
I'm trying to understand Ogden's lemma, and I know there are 4 cases, but in the next example I can only find 3:

Assume A = {$0^n1^m0^k$ | k = $max${n, m}} is CF:

Choose z = $0^k1^k0^k ∈ A$, z = xuvwy (with uw containing at least one 1):

u or w contains one 1 and one 0, so  $xu^2vw^2y ∉ A$
if w = ε, then u = $1^n$ so z = $xu^2vy$ = $0^k1^{k+n}0^k ∉ A$
if u = ε, then w = $1^n$ so z = $xvw^2y$ = $0^k1^{k+n}0^k ∉ A$

Am I doing this right? And what is the fourth case? Thanks in advance!


texts: What was the first programming language with loop break?

texts:
While tracing the history of the BREAK and CONTINUE statements found in popular languages, I ran into a dead end right around ALGOL.

Algol _? -> CPL -> BCPL -> C -> C++ -> Java -> JavaScript

What was the first programming language to introduce the feature of being able to break out of a loop from the body?

This feature existed in BCPL and is implied to have existed (from its manual) in CPL which was introduced in 1963.

ALGOL 60 was CPL's main influence, but ALGOL 60 did not have the feature.

The structured programming movement started around 1966.

Given the turmoil in the committee between ALGOL 60 and ALGOL 68 (which spawned many languages), was this the source of the feature? Did it exist under a different form at the time as a block EXIT perhaps?


texts:
Let $\text{ALL-CFG} = \{\left<G\right> \mid G\text{ is a CFG and } L(G) = \Sigma^*\}$.
I have understood the proof of ALL-CFG is undecidable, but I wonder why the following proof is not appropriate.
Let $C$ be a CFG. Then $\bar{C}$ is a CFG by closure under complement. Since the emptiness of CFG is decidable, we can use it to decide whether $\bar{C}$ is empty and therefore whether $C$ is universal.
This problem has confused me a lot. Really appreciate your help. Thanks!!!


texts: Show $x^y$ is a primitive recursive function

texts:
As this thread title gives away I need to prove $x^y$ to be a primitive recursive function.

So mathematically speaking, I think the following are the recursion equations, well aware that I am assigning to $0^0$ the value $1$, which shouldn't be, since it is an "indeterminate" form.

\begin{cases}
  x^0=1 \\
  x^{n+1} = x^n\cdot x
\end{cases}

More formally I would write:
\begin{cases}
  h(0) = 1 \\
  h(x,y+1) = g(y,h(x,x),x)
\end{cases}

as $g(x_1, x_2, x_3) = h\left(u^3_2(x_1, x_2, x_3),u^3_3(x_1, x_2, x_3)\right)$ and provided $h(x,y) = x \cdot y$ is primitive recursive.

Is my proof acceptable? Am I correct, am I missing something or am I doing anything wrong?


texts: Why can't configuration counting decide undecideable problems?

texts:
I know it might sound like a silly question, I just can't get my head around it...

I just read that $DSPACE(f(n))\subseteq DTIME(n\cdot 2^{O(f(n))})$.
The proof for it relies heavily on the fact that for a given $L\in DSPACE(f(n))$, the turing machine $M_L$ (which decides $L$ while consuming no more than $p(|x|)$ memory space for some polynomial $p$ and input $x$), under the assumption that it decides $L$, cannot have the same exact configuration twice (otherwise it's stuck in an infinite loop), and therefore, we can bound the runtime of $M_L$ by counting the number of possible configurations, which is $n\cdot 2^{O(f(n))}$.
The thing is this;
If ($M_L$ decides $L$) $\Rightarrow$ (There are no two similar configurations in $M_L$)
Why doesn't (There are two similar configurations in $M_L$) $\Rightarrow$ ($M_L$ won't decide $L$)?
Why can't configuration counting decide $A_{TM}$, for example? ($A_{TM}=\left\{(M,w)|M(w)=ACCEPT \right\}$)