texts: Is it possible to add every word in a file to a set in $\mathrm{O}(n)$ time?

texts:
The Problem:

I am currently analyzing a simple program that takes a file of length $n$, splits it into its individual words (seperated by white space) and adds those words to a set:

def file_word_set(name):
    with open(name) as f:
        res = set()
        words = f.read().split()
        res.update(words)
        return res

My Analysis:

Splitting a file of length $n$ into individual words takes $\mathrm{O}(n)$ time. The splitting will produce a list of $k$ strings where $0 \leq k \leq n$. These strings will be of varying length. Inserting a string into a set can be done in $\mathrm{O}(m)$ time where $m$ is the length of that string. This is because we must iterate through each of the characters of the array in order to determine its location in the underlying hash-table. Since the total length of all $k$ strings is no more than $\mathrm{O}(n)$, we will need to consider $\mathrm{O}(n)$ characters in total when building the set. Therefore the function takes $\mathrm{O}(n)$ time.

Is this correct?


texts:
How to prove that a $k$-universal family of hash functions is $(k-1)$-universal family?

I tried to prove it by definition of k-universal family of hash functions but I didn't know how to use the definition.

If I prove it, Is it necessary that a $1$-universal family of hash function is universal family?

Definitions:

Let $U$ be a universe of keys, and let $H$ be a finite collection of hash functions mapping $U$ to $\{0,\dots,m-1\}$.

$H$ is universal if $\forall x,y\in U$ where $x\neq y$: $\Pr[h(x)=h(y)] \leq \frac{1}{m}$ where $h$ is chosen randomly from $H$.

$H$ is k-universal if $\forall x_1,x_2,\dots,x_k\in U$ distinct elements and $\forall i_1,i_2,\dots,i_k\in \{0,\dots,m-1\}$: $\Pr[h(x_1)=i_1 \land h(x_2)=i_2 \land \dots \land h(x_k)=i_k] = \frac{1}{m^k}$ where $h$ is chosen randomly from $H$.


texts: What does this performance formula mean?

texts:
I have to make a quick clustering program but the following formula is gibberish to me:

  $\operatorname{Perf}(X,C) = \sum\limits_{i=1}^n\min\{||X_i-C_l||^2  \mid  l = 1,...,K\}$

  where $X$ is a set of multi-dimensional data and $C$ is a set of centroids for each data cluster.

This formula is a fitness function for an artificial bee colony clustering algorithm as a substitute for k-means clustering algorithm. It is described as a total
within-cluster variance or the total mean-square quantization error (MSE).

Can anyone translate it to pseudo-code, normal human English, or at least enlighten me?


texts:
i=2;
while(i<n)
{
   write('*');
   i=i*i;
}

Why $n ≃ i$?

I mean suppose $n=1000$ and so $i= 2,4,16,32,256,65536$ is in every steps.

In the book wrote $2^2 power(k)$ is pattern for growing $i$ so  $n ≃ i$ and...

Now 65536 or 256 isn't equal to 1000 or around 1000.

But why  $n ≃ i$?

This chapter is about notations.


texts: Shortest paths in isomorphic graphs with different edge weights

texts:
I'm looking for a way to find the shortest paths from a source to all destinations in isomorphic undirected graphs with different edge weights.

The only thing I can think of is using Dijkstra on each graph separately, but I was wondering if there is a way to take advantage of the isomorphism for a faster algorithm.


texts:
Is it true that Sequential Consistency is a stronger property than Cache Coherence?

According to

  Sorin, Daniel J; Hill, Mark D; Wood, David A: A Primer on Memory Consistency and Cache Coherence, Morgan & Claypool, 2011

sequential consistency can be described as (not formally):

  Sequential consistency memory model specifies that the system must appear to execute all threads’ loads and stores to all memory locations in a total order that respects the program order of each thread. Each load gets the value of the most recent store in that total order.

In other words, system is sequentially consistent, if given memory events (loads and stores) of each thread we can order all these events such that: 1) for each thread the order of its events is preserved, and 2) the global order is serial (any load returns latest value stored).

Now they continue and describe coherence:

  A definition of coherence that is analogous to the definition of Sequential Consistency is that a coherent system must appear to execute all threads’ loads and stores to a single memory location in a total order that respects the program order of each thread.

In other words, system is coherent, if given memory events of each thread for each location we can order events for that location, such that: 1) for each thread the order of its events to that location is preserved, and 2) for each location the order is serial.

Finally, they point out the difference:

  This definition highlights an important distinction between coherence and consistency: coherence is specified on a per-memory location basis, whereas consistency is specified with respect to all memory locations.

So it seems the difference is that for coherent systems we need a total order on all events for each location (thus the ordering between events for particular location), while for consistent systems the total order should be defined on the all events (and thus the ordering is also between events for different locations)?

Does that mean that coherence is less strict that consistency? (which seems amusing!) Are there traces that are coherent but not consistent?


texts: is there a constructive proof of the existence of a language which isn't recursive (without invoking infinities)?

texts:
My understanding is that a language cannot be decided if the language is actually infinite (not generated by any machine). However, actual infinites make me squirm. Is there any reason to believe in semi-decidable or undecidable languages other than a belief in actually infinite sets?
A positive answer to this question would confirm that there are, in fact, some Machines which present an insurmountable problem for decidability.
Edit: Still not resolved. Both answers use impredicative logic or prove something irrelevant.


texts: Subset sum problem with many divisibility conditions

texts:
Let $S$ be a set of natural numbers. We consider $S$ under the divisibility partial order, i.e. $s_1 \leq s_2 \iff s_1 \mid s_2$. Let

$\qquad \displaystyle \alpha(S) = \max \{|V| \mid V\subseteq S, V$ an antichain$\}$.

If we consider the subset sum problem where the multiset of numbers are in $S$ ,  what can we say about about the complexity of the problem related to $\alpha(S)$? It is simple to see if $\alpha(S)=1$, then the problem is easy. Note it is easy even for the harder knapsack problem when $\alpha(S)=1$$\dagger$.

$\dagger$ Solving sequential knapsack problems by M. Hartmann and T. Olmstead (1993)


texts: Which measure of sortedness explains the phase transition in Quicksort's runtime?

texts:
I'm currently creating a program to analyse the pathological cases of Quicksort. Namely, the transition of complexity from $O(n^2)$ to $O(n \log n)$ as a data set gets less ordered. Since Quicksort is a value-based algorithm, the choice of pivot determines its efficiency. We usually (Quicksort 3, and choosing a random element aside) select the first or last element as the pivot in an array. Therefore, since a good pivot is one that splits the array in half symmetrically, a more disordered array will make selecting a good pivot easier; or at least reduce the likely hood of running into the pathological case.

My program gradually randomises this array by swapping some elements each time. When I started to plot the graph of this using gnuplot I notice the trend I expected; a exponential distribution, branching off to a uniform distribution.

My question is, how do I quantify a level of disorder in a array? Is their a better way to gradually make an array of values more disordered?


texts: How is algorithm complexity modeled for functional languages?

texts:
Algorithm complexity is designed to be independent of lower level details but it is based on an imperative model, e.g. array access and modifying a node in a tree take O(1) time. This is not the case in pure functional languages. The Haskell list takes linear time for access. Modifying a node in a tree involves making a new copy of the tree.

Should then there be an alternate modeling of algorithm complexity for functional languages?


texts: Compression algorithms for small strings - building upon / extending Huffman


texts: How to select the maximum weight value for a bias node in a neural network?

texts:
I'm programming a neural network.  I know that I should initialize the network by picking random weights.  How do I pick a random weight for the connections to bias nodes?  What distribution should I use for these weights?  I can pick a random value from the range $[0,U]$, but what value should I use for the upper limit $U$?

What I've tried: I've set $U$ to correspond to the number of inputs to a neuron. Then the percentage of inputs '$K$' that the node needs to fire (this is set in the agents genome) which is set from 0.0 to 1.0, is multiplied with $U$ to get the weight of the bias node. So a node with a  $K$ value of 0.7 and 40 inputs would have a bias weight of $U * K = 0.7*40 = 28$.  Am I correct for assuming that $U$ would be the total number of a nodes inputs? Or am I approaching this wrong?


texts:
I'm interested in how the computer registers got their names, for example:
eax and ebx. I couldn't find anything.


texts: If $L$ is regular, must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular?

texts:
The reverse, $w^{R}$, of a string $w = w_1w_2...w_n$ is the string $w_n...w_2w_1$.  Suppose that L is a regular language.  Must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular?  Explain.

Intuitively, I suspect that $L_1$ may be nonregular, since the set of even-length palindromes of an arbitrary regular language $L$ isn't necessarily regular.  However, I'm not sure that the pumping lemma can be used to prove the non-regularity of $L_1$.


texts: Stratification of Bisimilarity : $\sim$ does not coincide with $\sim_\omega$

texts:
I am reading Sangiorgi's paper On the origins of bisimulation an coinduction.
Definition 2.5, on page 5, defines Stratification of Bisimilarity:

Let $W$ be the states of an LTS. We set:

$\sim_0 \overset{\text{def}}{=} W\times W$

$s\sim_{n+1} t$, for $n\geq 0$, if:
(1) for all $s^\prime$ with $s \overset{\mu}{\rightarrow} s^\prime$, there is $t^\prime$ such that $t \overset{\mu}{\rightarrow} t^\prime$ and $s^\prime\sim_n t^\prime$;
(2) the converse, that is, whenever for all $t^\prime$ with $t \overset{\mu}{\rightarrow} t^\prime$, there is $s^\prime$ such that $s\overset{\mu}{\rightarrow}s^\prime$ and $s^\prime\sim_n t^\prime$.

$\sim_\omega \overset{\text{def}}{=} \bigcap_{n\geq 0}\sim_n$

The paper follows with the remark that, in general, $\sim_\omega$ does not coincide with $\sim$ (the usual bisimilarity), and provides the following example (Example 2.6 in the paper) to highlight that:
We take the LTS with $\{a\}$ as the set of (arrow) labels, and the set of states is $\{a^0, a^1, \dots, a^\omega, s, t\}$, and the transition function $\overset{a}{\rightarrow}$ is the least function such that:

$a^\omega\overset{a}{\rightarrow}a^\omega$
$\forall n\geq 1, a^n\overset{a}{\rightarrow} a^{n-1}$
$\forall n\in\mathbb{N}, s\overset{a}{\rightarrow} a^{n}$
$\forall n\in\mathbb{N}, t\overset{a}{\rightarrow} a^{n}$
$t\overset{a}{\rightarrow} a^{\omega}$

which is represented in this picture:

The example then states:

It is easy to prove, by induction on $n$, that, for all $n$, $s\sim_n t$, hence also $s\sim_\omega t$.

However, I do not understand how that holds, even for $\sim_1$: $s\sim_1 t$ if (from item (2)):
whenever for all $t^\prime$ with $t \overset{\mu}{\rightarrow} t^\prime$, there is $s^\prime$ such that $s\overset{\mu}{\rightarrow}s^\prime$ and $s^\prime\sim_0 t^\prime$. Let's take $a^\omega$ as $t^\prime$, we indeed have $t\overset{a}{\rightarrow} a^\omega$. So, we have to find $s^\prime$ such that $s\overset{a}{\rightarrow} s^\prime$ and $s^\prime \sim_0 a^\omega$.
Hence my question : which state is suitable for such $s^\prime$, since $s\not\overset{a}{\rightarrow} a^\omega$ ?


texts: What are common formal techniques for proving functional code correct?

texts:
I want to provide proofs for parts of a Haskell program I'm writing as part of my thesis. So far however, I failed to find a good reference work.

Graham Hutton's introductory book Programming in Haskell (Google Books)—which I read while learning Haskell—touches on a few techniques for reasoning about programs such as

equational reasoning
using non-overlapping patterns
list induction

in chapter 13 but it's not very in-depth.

Are there any books or article you can recommend which provide a more detailed overview of formal proving techniques for Haskell, or other functional, code?


texts: Time complexity of languages that are polynomial time reducible to NP complete languages

texts:
I am wondering if given the time complexity of an NP-Complete problem or at least some information about it for example if $ SAT\in Time(2^{sqrt(n)})$ (hypothetically) could I assume that all languages in NP (which are clearly polynomial time reducible to SAT) are also $\in Time(2^{sqrt(n)})$

I believe the answer is false because I could basically pick any arbitrary class of exponential time functions and claim that all languages in NP are contained within it while it may actually belong to a class of higher power... but I'm not sure how to formulate this as a proof.


texts: Is Big-Oh notation preserved under monotonic functions?

texts:
I was just looking at the big-Oh notation. I wanted to know if the following is true in general
$$f(n)=O(g(n)) \implies \log (f(n)) = O(\log (g(n)))$$

I can prove that this is true if $g$ is monotonically increasing, but am not sure if this holds in general.


texts: Demonstration that EXP is closed under union complementation and concatenation

texts: How can I demonstrate that the EXP class is closed under union, concatenation, and complementation?


texts: How does an operating system create entropy for random seeds?

texts:
On Linux, the files /dev/random and /dev/urandom files are the blocking and non-blocking (respectively) sources of pseudo-random bytes.

They can be read as normal files:

$ hexdump /dev/random
0000000 28eb d9e7 44bb 1ac9 d06f b943 f904 8ffa
0000010 5652 1f08 ccb8 9ee2 d85c 7c6b ddb2 bcbe
0000020 f841 bd90 9e7c 5be2 eecc e395 5971 ab7f
0000030 864f d402 74dd 1aa8 925d 8a80 de75 a0e3
0000040 cb64 4422 02f7 0c50 6174 f725 0653 2444
...

Many other unix variants provide /dev/random and /dev/urandom as well, without the blocking/non-blocking distinction.

The Windows equivalent is the CryptGenRandom() function.

How does the operating system generate pseudo-randomness?


texts:
This question is related to Master Theorem on oscillating function.

Consider a recurrence of the form

$T(n) = a T(n/b) + f(n)$

Master Theorem's regularity condition excludes some cases (for example, when $f(n)$ is oscillating).

Suppose, however, that $f(n)=\Theta(g(n))$ for a function $g(n)$ that does not violate the regularity condition, so that the Master Theorem is applicable if $g(n)$ is used instead of $f(n)$.
Consider then the following recurrence:

$T'(n) = a T'(n/b) + g(n)$

and assume that the master theorem gives the solution $T'(n)=\Theta(g(n))$.

Can I then safely conclude that $T(n)=\Theta(g(n))$? Or there are some reasonable conditions on $g(n)$ we can add (I suppose that if $g(n)$ is polinomially bounded then maybe Akra-Bazzi method will apply, even if one have to swich integration and $\Theta$, and I'm not sure this is sound)?

Notice that from $f(n)=\Theta(g(n))$ we cannot deduce that $f(n)$ is always less than or equal to $g(n)$ or to a $d\cdot g(n)$ for some fixed $d$ (indeed, $g(n)$ can be equal to 0 for some value of $n$, so I'm not totally convinced by the answer to Regularity condition in the master Theorem in the presence of Landau notation for f as it is not possible to prove the base case of the induction, unless one changes the initial condition). So I cannot prove by induction that $T(n)<T'(n)$ for all $n$ and, anyway, I only want to prove $T(n)=\Theta(T'(n))$.

To give some context, this is the case I want to apply the result to: consider the recurrence

$T(n)=2\cdot T(n/2)+f(n)$

where I only know that $f(n)=\Theta(n\sqrt{n})$. Then I can unfold the recurrence obtaining
\begin{equation*}
\begin{split}
T&(n)=2T\left(\frac{n}{2}\right)+\Theta(n\sqrt{n})=
2\left(2T\left(\frac{n}{4}\right)+\Theta\left(\frac{n}{2}\sqrt{\frac{n}{2}}\right)\right)+\Theta(n\sqrt{n})
=\\
&=\ldots=2\left(2\left(2\ldots \left(2T\left(\frac{n}{2^h}\right)+\Theta\left(\frac{n}{2^{h-1}}\sqrt{\frac{n}{2^{h-1}}}\right)\right)\ldots\right)\right)+\Theta(n\sqrt{n})
\end{split}
\end{equation*}

until $2^h=n$, i.e. $h=\log(n)$. Then $T(n)=\sum_{i=0}^{\log(n)-1} 2^i\cdot\Theta\left(\frac{n}{2^i}\sqrt{\frac{n}{2^i}}\right)$.

Performing the calculations I get
\begin{equation*}
\begin{split}
T(n)&=\sum_{i=0}^{\log(n)-1} 2^i\cdot\Theta\left(\frac{n}{2^i}\sqrt{\frac{n}{2^i}}\right)=\Theta\left(\sum_{i=0}^{\log(n)-1} 2^i\cdot\frac{n}{2^i}\sqrt{\frac{n}{2^i}}\right)=\\
&=\Theta\left(n\sqrt{n}\cdot\sum_{i=0}^{\log(n)-1} \frac{1}{\sqrt{2^i}}\right)
\end{split}
\end{equation*}
The series $\sum_{i=0}^{+\infty} \frac{1}{\sqrt{2^i}}$ is convergent, so I can conclude (I hope correctly) that $T(n)=\Theta(n\sqrt{n})$.

On the other hand, I cannot directly apply Master Theorem, as from $f(n)=\Theta(n\sqrt{n})$ I cannot conclude $2f\left(\frac{n}{2}\right)<cf(n)$ for some $c<1$. Indeed, if definitively we have $c_1 n\sqrt{n}\leq f(n)\leq c_2 n\sqrt{n}$, then

$f(n)\geq c_1 n\sqrt{n}= 2\sqrt{2}c_1 \frac{n}{2}\sqrt{\frac{n}{2}}\geq\frac{2\sqrt{2}c_1}{c_2}  f\left(\frac{n}{2}\right)=\frac{\sqrt{2}c_1}{c_2}  2f\left(\frac{n}{2}\right)$

and so

$2f\left(\frac{n}{2}\right)\leq \frac{c_2}{\sqrt{2}c_1} f(n)$

but $\frac{c_2}{\sqrt{2}c_1}$ is not necessarily less than 1.


texts: Is there any technique to prove that a given language L is not ambiguous context-free? Here I don't know that whether L is CFL or not.


texts: Find a lambda term satisfying two equations

texts:
I'm just looking for the general idea on how to approach the following problem:

Find a term $\Delta=\lambda x.xUV$ such that:

$\Delta\Delta=K$
$\Delta K=S$

(it's a system of 2 equations, I didn't know how to format it properly)

Where $K=\lambda xy.x$ and $S=\lambda xyz.xz(yz)$

I think I need to use Bohm theorem but I don't know exactly how.


texts: Prove that set of operations form a commutative Monoid

texts:
this is my first post on this exchange.

I am looking for some help with defining a proof that a set of operations I have designed forms a commutative monoid.

(Disclaimer: I am not sure that I have phrased the question properly so I will be very grateful for restructuring it if necessary.)

I think it will be better if I illustrate what my problem looks like:

I assume that:

$\exists cm(t) \in CM$

means that there exists an instance of $commutative \space monoid$ for type $t$.

Given

$k \in Keys$

$op \in \{NoOp, Add, Read, Write\}$

$tr \in \{Identity, Write(k, v), Add(k, v): \exists cm(v) \in CM\}: \forall k \in K$

Point of this description is to allow for easier detection of conflicts when more than one process wants to modify the value under some key. My mental model for this is close to optimistic concurrency control (or optimistic locking) married with CmRDT.

Every process $p$ operates on the "copy" of some state. When p wants to access value under key $k$ this fact is recorded in the form of $(Key, Op, Transform)$ tuple. (note: that $Add$ transformations are allowed only if there exists an instance of $commutative \space monoid$ for this type).

We define an instance of $commutative \space monoid$ for $Ops$:

$$\begin{array}{c|c|c|c|c}
             & \text{NoOp} & \text{Read}  & \text{Add}   & \text{Write} \\ \hline
\text{NoOp}  & \text{NoOp} & \text{Read}  & \text{Add}   & \text{Write} \\ \hline
\text{Read}  & -           & \text{Read}  & \text{Write} & \text{Write} \\ \hline
\text{Add}   & -           & -            & \text{Add}   & \text{Write} \\ \hline
\text{Write} & -           & -            & -            & \text{Write} \\ \hline
\end{array}$$

(matrix is symmetric so I omitted the lower left half). Note that $Read *  Add$ becomes a $Write$. My reasoning behind it is that $Read$ may influence $Add$-ed value so it should not commute with anything else.

When $p$ executes an engine records operation it performs on every $k$ and uses rules defined above so that later it is easy to decide which operations conflict:

  Two operations on key $k$ conflict if any of them is $Write$.

Now, what I want to prove? I want to prove myself and to my management that operations, defined by above algorithm as non-conflicting, will never lead to inconsistent state. Inconsistent state is defined as one in which order of executing transformations changes the final value.

I tried coming up with a description in $TLA^+$ and $F^*$ but I am not an expert in either of them. My level of understanding category theory (and math in general) is not superb either. Can you please help me coming up with proper definition of this?


texts: Use or Importance of $\Rightarrow^*$ operator

texts:
Particularly, there are 2 variants of $\Rightarrow$, one is $\Rightarrow^*$ and another is $\Rightarrow^+$ which are used in derivation of strings using the productions of the grammar.

As stated here, when $\Rightarrow^*$ is used, it means derive in 0 or more steps and when $\Rightarrow^+$ is used, it means derive in 1 or more steps.

What I don't understand is what is the use or importance of $\Rightarrow^*$ operator?. It just replaces the head of the production with the head itself.
Is it that the $\Rightarrow^*$ operator is just there to define operators in some standard way or it actually differs in the way it is used as compared to $\Rightarrow^+$?

Also, while deriving strings, to skip some obivious steps(like replacing multiple non-terminals in a string with their respective terminals), should I use $\Rightarrow^*$ or $\Rightarrow^+$?


texts: DFA - Accept all strings that does not contain a certain substring

texts:
So I have been trying to create a Deterministic Finite Automaton(DFA) in Jflap that accepts all strings from the alphabet {a, b, c} except those that contain the substring "abc". However i keep running into issues where certain strings that should be allowed aren't, such as "acbc". Do you have any tips or tricks that can be used to get around these kind of issues?
DFA that accepts any string that contains substring "abc" below


texts: Can literals in functional languages be thought of as functions from the empty type?

texts:
A while ago, I think on Stack Overflow, I saw someone say that Haskell literals can be thought of as functions that don't operate on anything. This makes sense to me but I remember someone else vehemently disagreeing with him.

If I understand correctly, all values in primitive types, or at least those in Bool, are type constructors, and type constructors are a special kind of function into the type. Since values like 2.87, True, or 'f' don't have any parameters passed to them it seems like it wouldn't effect the semantics of the language whether you think of them just as elements of their type or a functions from a type containing nothing into their type that always returns their value. Is there anything wrong with thinking of literals in this way?


texts: Will random function ever hit a hard coded decimal number?

texts:
I'm not very sure how exactly a fractal number is stored nor how random function works in mordern programming languages.
But I am curious, will random function ever hits a hard coded decimal number?
I know mathematically it is impossible, but how about in computer science?
Such as the following javascript code, will it ever hit the number and stop?
// this can be any number
const rnd = 0.123456;

while (true) {
    if(rnd === Math.random()) {
        console.log('hit');
        break;
    }
}

Also I ran that code for 2 hours and it didn't stop

If decimal points are store in 64 bit, does that mean the chance to hit any decimal point is 1/2^64?
If it can hit, is 0.000123456 harder to hit than 0.01?


texts: What is the maximum directly adddressable memory capacity?

texts:
This is taken from OPERATING SYSTEMS: INTERNALS AND DESIGN PRINCIPLES by WILLIAM STALLINGS

Consider a 32-bit microprocessor composed of 2 fields: the first byte contains the opcode and remainder an immediate operand or an operand address.
What is the maximum directly addressable memory capacity?

Now the answer should be 2^24=16777216 bits = 2 megabytes but the solution set says 2^24=16 MBytes

So am I wrong or is the solution set wrong?


texts: Check if the regular expression r made up of the single symbol alphabet Σ = {a} defines language L(r) = a*

texts: I have got to write an algorithm programatically using haskell. The program takes a regular expression $r$ made up of the unary alphabet $ \Sigma = \{ a \} $ and check if the regular expression $r$ defines  the language $L(r) = a^{*} $. I am looking for any kind of tip, I think I can use a pumping lemma somehow, but I am not sure how exactly.


texts: For two sets of points find if second one is result of linear transformation of the first

texts:
Say we have two sets of points in vector-2 space (In actuality need to solve this problem in vector-3 space but decided to start with a simpler problem). The points in the second set are the result of transformation of the points in the first set. It's not known which point in the first set corresponds to which point in the second set. What needs to be calculated is if the points of the second set can be seen as the linear transformation of the first set. So basically finding whether there exists a 2 by 2 matrix, which if applied to the first set gives the second set. And if so calculating it.
Should a problem like this be solved using computational geometry, like sweep line algorithm to compare all points between sets?


texts: I've been trying to find the most efficient unification algorithm by following reference chains on the Wikipedia article on unification. As far as I can tell, the fastest one is the one presented in "A Practical Unification Algorithm", but is there a faster one?


texts:
Hi i have derived the following SoP (Sum of Products) expression , by analyzing the truth table of a 3 bit , binary to gray code converter. I ask for verification, because i feel as though this answer may not be correct or complete.

  X = a'bc' + a'bc + ab'c' + ab'c

which, using k-maps, was simplified to

  X = ab' + a'b

Is this correct  ?


texts: Why do I always have something missing in my understanding of topics which always lead me to solve problems incorrectly?

texts:
I am a computer science masters student, I come from a background of engineering and not CS. My problem is whenever I have a problem set, a programming task or an exam, I always try hard to understand the question and think for the right answers, but I usually either get stuck or have a wrong answer. When I seek help I figure out I wasn’t completely understanding the topic of the question itself, missing some part of the information or even having a wrong understanding to some parts.
So my question is, how can I approach a computer science topic "for e.g. operating systems" and have a good understanding with the right depth, to have a better comprehension and to be able perform better at programming  tasks and exams.


texts: Is this finite graph problem decidable? What factors make a problem decidable?

texts:
I want to know if the following problem is decidable and how to find out. Every problem I see I can say "yes" or "no" to it, so are most problems and algorithms decidable except a few (which is provided here)?

  Input: A directed and finite graph $G$, with $v$ and $u$ as vertices
  Question: Does a path in $G$ with $u$ as initial vertex and $v$ as final vertex exist?


texts:
Currently while I was coding, I got a doubt.

While I was solving a particular type of problem I found it to be solved in    $O(n^3)$.

I have broken that problem and solved it in $O(n^2)$.

But to solve it I have broken that $O(n^3)$ to $3$ * $O(n^2)$

Is it a better solution than $O(n^3)$ or will it matter the number of $O(n^2)$ also?


texts:
So I am working on a question that requires me to find the linear address.

Here's some information:
Main memory size is 8GB, which translates to $2^{3} * 2^{30} = 2^{33}$.
Block size is 16KB each, which translates to $2^{4} * 2^{10} = 2^{14}$.

I was then required to find:

(i) The number of blocks in main memory:
 $2^{33}/2^{14} = 2^{19}$ blocks.

(ii) The number of bits required to address a block:
$19$ bits.

(iii) The number of bits required for an offset within a block.
I am not so sure if I did this bit correctly, but I ended up with:
$2^{14}$ bits.

These are the parts that I'm having trouble calculating or knowing what to do. Can I be guided accordingly, please?
(iv) The linear address for:
(a) Block 32, byte 100 (b) Block 1000 byte 1800.

(v) The block and offset of a byte for the linear address:
(a) 32431 (b) 232156


texts: find the actual size of an object from pixel coordinates

texts:
I am quite new to vision and OpenCV, so forgive me if this is a stupid question but I have got really confused.

My aim is to detect an object in an image and estimate its actual size. Assume for now I only want length and width, not depth.
Lets say I can detect the object, find its size(length and width) in pixels and I have both the intrinsic and extrinsic parameters of the camera.

The documentation of camera calibration as I understand says that the intrinsic and extrinsic camera parameters can be used to transform from camera coordinate system to world coordinate system. So this should mean converting from pixel coordinates to real coordinates right? And so I should be able to use pixel size and these params to find the real size?

But, say the object is photographed at different depth (distance from camera), then its size would come out different using above method. So.....what does it mean transforming from camera to world coordinates?

Any kind of explaination/links/help would be highly appreciated.


texts: Building a verifier for sentences involving addition over the natural numbers

texts:
Consider the model $(\mathbb{N},+)$; that is, the natural numbers equipped with the addition relation, PLUS($x$,$y$,$z$), where PLUS($x$,$y$,$z$) is true iff $x + y = z$. Let Th$(\mathbb{N},+)$ be the theory of this model; that is, the set of true sentences in the language of the model. For example, the sentence $\forall x \exists y [x + x = y]$ is a true sentence in this model. Let's assume for simplicity that all of these sentences are in prenex normal form.

I'm interested in coming up with either an (efficient) verifier for Th$(\mathbb{N},+)$ or a nondeterminstic algorithm that decides Th$(\mathbb{N},+)$. In the former case, I'm wondering what a certificate could be. If all of the quantifiers in the input statement are existential, this isn't a problem: a certificate would just be an assignment of all the variables. However, things are made difficult when the input has a universal quantifier, since it isn't obvious how we can check that something holds for all members of an infinite set.


texts: How come code re-usability is a benefit of Bottom-Up software development?

texts:
Re-usability of code is one of the main benefits of the bottom-up approach
(Wikipedia)

I can't quite figure out how bottom-up approach enables code re-usability. I am aware that Object Oriented Programming is bottom-up approach and it has features such as inheritance that enable code re-usability. But I cannot connect bottom-up with code re-usability intuitively.


texts:
One topic I've recently looked at is co-occurence networks formed from Twitter tweets.  This is how I felt after looking at the tweets of random people:

This leads me to the question:

  Question: Is it possible to discern the quality of web data from networks derived from it?

A hypothetical situation: Suppose we have two networks of comparable size derived from two different web sources: Network X is from a high-quality source (perhaps government documents) and Network Y is from a low-quality source (perhaps some random blog).  Which network is from a higher quality source: Network X or Network Y?

I'm intentionally leaving out specifics about the networks in this question, since I'm intending this to be more of a proof-of-concept style question.


texts:
For my course I have to memorise a number of algorithms and to know how to perform them by hand. The steps of the quick sort are given as the following in the text book I am using:

Choose the item at the midpoint of the list to be the first pivot
Write down all the items that are less than the pivot, keeping them in order, in a sub-list
Write down the pivot
Write down the remaining items (those greater than the pivot) in a sub-list
Apply steps 1 to 4 to each sub-list
When all items have been chosen as pivots, stop

The problem is that these instructions are ambiguous as to what to do if there is an item which is equal to the pivot. Does it fall into the first sub-list (written before the pivot) or the second (written after the pivot)? I assume that there is some sort of agreed upon standard for this.


texts: Runtime analysis of a "find the secret number" algorithm

texts:
The algorithm task is to find an integer (range is not known). the function guess(num) returns one of three chars: '>','<' or '='.
  Find the secret number with O(logS) guesses, where S is the secret number.  You can use find_secret(N1, N2) which operate with O(log(N2-N1)).. What it does is simply a binary search.

So, the algorithm implemented (with Python) as follows:

def find_secret2():
    low = 1
    high = 2
    answer = guess(high)
    while answer == ">":
        low *= 2
        high *= 2
        answer = guess(high)

    if answer == "=":
        return high
    return find_secret(low, high)

my thoughts about the complexity of this algorithm:

it takes O(logS) to reach the range where low < secret < high.
then, it takes O(log(high-low)) - because we're using find_secret(N1, N2) method.

I'll be glad if you could help me explain why the algorithm's complexity is O(logS) in a mathematical/rigorous way using the O-notation.
Thanks!


texts: Is this case of weighted 2SAT NP-complete?

texts:
Weighted 2SAT asks if it is possible to satisfy the formula with at most $k$ variables set as positive/negative. Trivially, every instance must be in 2CNF. It is known to be $\mathsf{NP}$-complete.

We have following additional restriction: each variable appears twice as positive and once as negative or vice versa.

Example of instance:

$(x\lor y)\land(x\lor z)\land(\overline x\lor t)\land(\overline y\lor z)\land(\overline y\lor \overline t)\land(\overline z\lor \overline t)$

Is this weighted 2SAT variant $\mathsf{NP}$-complete?

Of course, if vertex cover where each vertex has only 2 edges is $\mathsf{NP}$-hard, this also must be $\mathsf{NP}$-hard. So, if such result is known, then it also can be an answer. Ah, well, this does not help.


texts: Dominating set of given size $k$ in $O(2^k |V| |E|)$

texts:
Recently I've encountered an interesting case of dominating set problem: given an unweighted and undirected graph $G(V, E)$ and knowing that it contains a dominating set of size $k$, find any such dominating set in time $O(2^k\ \vert V \vert\ \vert E \vert)$.

During my research, I found only some algorithms to find fixed-size dominating set in a $d$-degenerated graphs, but no such restriction is applied in this problem.

Is there any way to solve that problem in such time?


texts: Understanding expected time bound for unsuccessful search in R-way tries

texts: As per Tries slides (page 17) from Algorithm 4th edition book by Robert Sedgewick, the asymptotic expected runtime for an unsuccessful search in $R$-way tries miss is $O(\log_R N)$. Can someone please explain how this number can be derived?


texts: Clustering a set of point by affine transform

texts:
We are given a set of $n$ points on the plane $a_i = \{x^a_i, y^a_i\}$ and $b_i = \{x^b_i, y^b_i\}$.
Assume that the points b are an affine transform of the points a, we can find a matrix $M$ and vector $t$ such that $\sum_{i=0}^{n-1} ||M a_i + t - b_i ||^2$ is minimized, in fact, we can even do so analytically.
Assume however that the points a_i are composed of different subsets to which a different affine transform was applied.
Let $\epsilon$ be a small, tolerance value. A partition $\cup_{j=0}^m P_j = [1\ldots n] \wedge \forall j, k, P_j \cap P_k = \emptyset$ is said to be admissible iff
$$\forall j,~ \exists M_j, t_j,~ \forall i \in P_j,~ ||M_j a_i + t_j - b_i||^2 < \epsilon$$
Simply speaking, we partition the points into different subsets each of which is sent to $b$ with its own affine transform.
An admissible partition always exists because it's always possible to sent a to b exactly if each point is given its own affine transform (in fact, every 3 points can be sent to any other 3 points).
We want to cut up the points in as few pieces as possible: an admissible partition is minimal when it has fewer or equal subsets than any other admissible partitions.
How would one go about finding an admissible partition? Heuristics and approximate solutions are welcome. One approach would be to consider the transformation defined by every triplet of points and try to cluster those together, but this requires looking at $O(n^3)$ transforms.


texts: Pairwise independent hash function family?

texts:
I am looking for a family of pairwise independent hash functions $\mathcal{H} = \{h \mid h:[n]\rightarrow [m]\}$ that is easily computable.
As an example that doesn't seem to work, choose a prime $p > n$  and $a,b \in \{0,\dots, p-1\}$ independently and uniformly at random. Now let $h_{a,b}(x) = ax+b \bmod p \bmod m$. Sadly I don't think this is uniform because of the final $\bmod m$.
What can one use instead?


texts: Is there a dual concept to "Turing Complete" in logic?

texts:
Two computing models can be shown to be co complete if each can encode a universal simulator for the other.  Two logics can be shown to be co complete if an encoding of the rules of inferences (and maybe axioms if present) of each be shown to be theorems of the other.  In computability this has led to a natural idea of Turing completeness and the Church Turing Thesis.  However, I have not seen where the logical co completenesses has led to any naturally induced idea of total completeness of similar quality.

Since Provability and Computability are so closely related, so I think it isn't too much to consider that there could be a concept in logic that is a natural dual to Turing Completeness.  Speculatively, something like: there is a "true" theorem that isn't provable in a logic if and only if there is a computable function that isn't describable by a computing model.  My question is, has anyone studied this?  A reference or some keywords would be helpful.

By "true" and "computable" in the previous paragraph I'm referring to the intuitive but ultimately undefinable ideas.  For example, someone could show that the finiteness of Goodstein sequences is "true" but not provable in Peano arithmetic without fully defining the concept of "true".  Similarly, by diagonalization it can be shown that there are computable functions that are not primitive recursive without actually fully defining the concept of computable.  I was wondering, even though they tend to ultimately be empirical concepts, perhaps the concepts could be related to each other well enough to relate the concepts of completeness.


texts: Help need to learn Quantum Computation and Information

texts:
I want to learn quantum computation and information. I am studying from Nielsen & Chuang book for this.
Is there any online vedio (lecture series) starts from
basics of quantum computation and information up to factorization, discrete log, search etc?


texts: Performing semantic segmentation on images on word documents

texts:
At the moment, I'm making a comparative analysis between two different neural networks for a class. The problem they are both trying to solve is detecting tables on documents. Below is an example of one:

One of the algorithms I am analyzing is a fully convolutional network. The way the algorithm works is that it goes pixel by pixel and assigns each pixel a label of which class it could be in (in my case, table or not a table).

However, my issue is how should you pre-process/label your data if you're training one of these networks? Because tables themselves have words on them, looking at such a fine resolution to detect tables is not optimal. It would be preferable if I could have the FCN look for structural elements that help us identify tables (big gaps, columns, header, etc).

I'm not sure how to train a network that goes pixel by pixel to search for the bigger structural elements. Any thoughts on this?


texts: Showing that $n\log n - n$ is $\Omega(n)$

texts:
Prove that $n\log{n} − n$ is $\Omega(n)$.

I do know the answer:

$\log{n} ≥ 2, \forall n \ge 4$.

Thus, $n\log{n}−n\ge n ,\forall n\ge 4 \implies n \log n − n ∈ Ω(n)$.

But can someone please explain how  its done. where did $2$, $\forall n$ and $4$ came from.
Then how was $n, \forall n \ge 4$ added.


texts: Tackling overlearning neural network issue

texts:
I'm trying to train a neural network using this sort of data (for a homework):
Number of Features : 42,
Target data : 0 or 1,
Number of Samples : 111 Individuals ( 69 Cases + 42 Controls )

However i'm facing an over-learning issue (the learning curve approaches the goal set, however the validation curve shows no improvement): the learning stops after less than 15 iterations because of a great number of validation fails: no improvement in the quality of validation tests.
I managed to have great results by using 444 (4*111) examples in my training as I repeated the initial data four times. but i'm not sure if this is clean.
In other words, is it alright to repeat existing examples to have more values for training ?

Thanks in advance.


texts: Maximum number of points that two paths can reach

texts:
Suppose we are given a list of $n$ points, whose $x$ and $y$ coordinates are all non-negative. Suppose also that there are no duplicate points. We can only go from point $(x_i, y_i)$ to point $(x_j, y_j)$ if $x_i \le x_j$ and $y_i \le y_j$. The question is: given these $n$ points, what is the maximum number of points that we can reach if we are allowed to draw two paths that connect points using the above rule? Paths must start from the origin and may contain repeated points. $(0, 0)$ is of course not included in the points reached.

An example: given $(2, 0), (2, 1), (1, 2), (0, 3), (1, 3), (2, 3), (3, 3), (2, 4), (1, 5), (1, 6)$, the answer is $8$ since we can take $(0, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4)$ and $(0, 0) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (1, 5) \rightarrow (1, 6)$.

If we are allowed to draw only one path, I can easily solve the question by dynamic programming that runs in $O(n^2)$. I first sort the points by decreasing $x_i+y_i$. Let $D[i]$ be the maximum number of coins that one can pick up from coins $1$ to $i$ in the sorted list. Then $D[1] = 1$ and $D[i] = \max\limits_{1\le j < i, x_j \le x_i, y_j \le y_i} D[j] + 1$. The answer then is just $\max\limits_{1\le i \le n} D[i] + 1$.

But I cannot come up with a recurrence relation for two paths. If anyone has any idea about such a recurrence relation, I would be happy to hear what they are.


texts: What to expect in a Computer Science and Mathematics course?

texts:
I'm a high school student. I'm really into programming and mathematics and planning to study CS and mathematics when finished with high school.

I have a couple of questions concerning this issue:

Firstly, from maths point of view, what are the prerequisites and what subjects do I get in the first 2 years? I understood that Linear Algbera and Discrete mathematics are very important! So can you name an example of a maths textbook I may get?

Secondly, from a CS point of view, I already 'know' C#, F# and sometimes I play around with JS. Is it obligatory to learn ANOTHER language like python, java or c++? since knowing C# and F# already fulfils the 'need' of knowing different languages, F# with it's elegant functional-first programming paradigm and C# for imperative-first programming (technically, both F# and C# are multi-paradigm, which is awesome!)

To be more specific, I am into computer vision and ML. what textbooks do you think I may get in this area?


texts: What is the reason of inaccuracy of operations on float numbers?

texts:
I wonder why in JavaScript

0.1 + 0.2  // return 0.30000000000000004

4%0.1 // return 0.09999999999999978

http://jsbin.com/oHISAfU/1/edit  (Example)

In C the math.h library fmod function

printf("%f", fmod(4.0,0.1));  // print 0.100000

http://ideone.com/RG5Wyv (Example)

And in Spotlight (search feature in the Mac OS X ~ I already submit bug report) that support math operation

4%0.1 = 0.1


texts: Automorphism of a Graph with a given Set of Permutations

texts:
Given a graph $H$.  A set of permutations $\alpha$ which contains permutations of vertices of $H$.

The permutation set $\alpha$ has  automorphisms of subgraph $H_1, H_2,..... H_x$ where $x$ is the number of total subgraphs. These subgraphs are connected. These permutations can be extended to the automorphism of $H$. By extending, we mean that  automorphism of subgraphs can be extended to the automorphism of graph $H$. This concept is similar to E. Luks' paper of graph siomorphism of bounded valence.

Each subgraph has constant number of vertices. The adjacency matrix of $H$ is -

$$H = \begin{bmatrix}
H_{(x)} & R_{(x, x-1)} & R_{(x,x-2)} & \dots & \dots & R_{(x,1)} \\
R_{(x,x-1)^{T}} & H_{(x-1)} & R_{(x-1,x-2)} & \dots & \dots & R_{(x-1,1)} \\ \vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\
R_{(x,1)^{T}} & R_{(x-1,1)^{T}} & R_{(x-2,1)^{T}} & \dots & \dots &H_{1} \end{bmatrix}$$

The adjacency matrix of graph $H_k \cup  H_e$ is $M_{(k,e)}$ where   $M_{(k,e)} =\left( \begin{array}{ccc} H_e & R_{k,e} \\ R_{k,e}^{T} & H_k\\ \end{array} \right) $,  where, $R_{k,e}$ is the non symmetric sub-matrix of adjacency matrix $H$.  Here, $R_{k,e}$ represents  edges  between $H_k,  H_e$.

Problem: How to find  an automorphism of $H$ in polynomial time (in $\alpha$)?

Note:

$\alpha$ is the generating set of autmorphsim group of  $H$.


texts: One of my final exam questions asked me to give a Turing-unrecognizable language over an unary alphabet, which I wasn't able to complete, but I ended using the Busy Beaver function (BB(k)) which is known to be something intractable or uncomputable  so that I constructed the language as a set of strings 1^BB(k) for natural number k=1,2,... It intuitively feels like it's Turing unrecognizable but how can I prove it(if this is true)?


texts: What fragment of Martin-Löf dependent type theory can be expressed using generic types in Java?

texts:
I have recently come to realize that a number of problems I had a few years ago trying to implement various mathematical theories in Java came down to the fact that the typing system in Java is not sufficiently strong to model all of Martin-Löf dependent type theory.

Prior to Java 5 and generics, the only type theory you could do was through classes and interfaces, which give you arbitrary types built out of the ground types int,double,char and so on using product and function types.  You can also build recursive types such as Lists, though not in a uniform way.

Using generics, you can do a bit more.  You can now define List<T> as a function
$$
\DeclareMathOperator{\Type}{Type}\Type\to\Type
$$
and so we get higher order types.

This is not the end of the story, though.  Using a generics trick, we can model some dependent product types.  For example, we can define types of the form
$$
\prod_{T\colon\Type}f(T)
$$
using the syntax

public interface f<T extends f<T>>
{
  // We can now refer to T as much as we like
  // inside the class.  T has type f<T>.
}

As an example, we can model the basic underlying structure of a monoid (but not the associativity and unitality conditions) using a term of type
$$
\prod_{T\colon\Type}T\times (T\to T\to T)
$$
(i.e., a set $T$ with a designated unit element and a binary operation on $T$).  Using Java generics, we can model this type:

public interface MonoidElement<T extends MonoidElement<T>>
{
  public T unit();

  public T mul(T op1, T op2);
}

However, when we try to model more complicated concepts, the type theory breaks down.

Is there a simple description of the fragment of MLTT corresponding to the types that can be built in the Java typing system?


texts: How to find the maximal set of elements $S$ of an array such that every element in $S$ is greater than or equal to the cardinality of $S$?

texts:
I have an algorithmic problem.

Given an array (or a set) $T$ of $n$ nonnegative integers. Find the maximal set $S$ of $T$ such that for all $a\in S$, $a\geqslant |S|$.

For example:

If $T$=[1, 3, 4, 1, 3, 6], then $S$ can be [3, 3, 6] or [3, 4, 6] or [4, 3, 6].
In $T$=[7, 5, 1, 1, 7, 4], then $S$ is [7, 5, 7, 4].

I have tried this recursive function.

function(T):
    if minimum(T) >= length(T):
        return T
    else:
        return function(T\minimum(T))

Is there any non-recursive algorithm. (I did not check my recursive algorithm, so it could has some flaw.)


texts:
Although I know that the Hamilton Path problem is ${\sf NP}$-complete, I think the following variant can be solved in polynomial time:

  Given a planar graph with vertex set $V$, edge set $E$, start node $S$ and target node $F$,
  our task is to find the Hamiltonian path from $S$ to $F$ or write that the path doesn't exist.

  Last condition: In the path, in addition to selecting the directly connected vertices,
  we can also choose those connected to exactly one neighbor.

  Edit: The degree of any vertex is at most four ($\deg(v_i) \le 4$).

Does anyone have any ideas how to prove that this can be solved in polynomial time?

It can be hard to understand, so I will give an example:

In the left example, for $S=1,F=12$, the solution is the path $1, 11, 8, 7, 5, 9, 2, 10, 4, 6, 3, 12$.

In the right example, for $S=1,F=15$, there is no Hamiltonian path.


texts: Interleave two arrays such that collisions are minimised (dynamic programming)

texts:
This is a fascinating bioinformatics dynamic programming that I am solving. I am not looking for an answer to the problem, but rather any algorithms, research papers, or other pointers that could be helpful.

SETUP

You are working in a lab as a microbiologist and would like to formulate an algorithm to interleave two DNA sequences m and n to form a larger DNA sequence k.

m and n are comprised of the elements a, b, and c.

For example:

m = [a, b, c, c, a]

n = [b, a, c, c, a]

The italic elements represent members of m, and bold elements represent members of n.

THE PROBLEM

As stated above, we would like to use dynamic programming to interleave the elements of m and n to form a larger sequence k. Some examples of k could be:

k = [a, b, a, c, b, c, a, c, c, a]

or

k = [b, a, c, c, a, a, b, c, c, a]

Note that the elements of m must appear in k in the same order that they appeared in m, the same applies to the elements of n.

FURTHER COMPLICATIONS

A collision occurs if >= 2 elements of the same type are contiguous in k. Three examples are if k contains the sub-array [a, a] or [b, b, b] or [c, c].

If there is a collision of a's a penalty of u is applied for every consecutive a.

If there is a collision of b's a penalty of o is applied for every consecutive b.

If there is a collisions of c's a penalty of p is applied for every consecutive c.

For example:

A subarray of [a, a, a] in k will incur a penalty of u*3.
A subarray of [b, b] in k will incur a penalty of o*2.
A subarray of [c, c, c, c] in k will incur a penalty of p*4.

OUR TASK

We would like to use dynamic programming to interleave m and n to form k such that the total collision penalty is minimised.

EXTENSION

Complete the task with minimal space and time complexity.


texts: What's the decoding time complexity of LT codes?

texts:
LT codes are practical fountain codes that are near-optimal erasure correcting codes.

Simply stated, for encoding a $n$-block message, each packet first chooses a degree $d\in\{1,\ldots,n\}$ according to a specific distribution, and then $d$ random blocks are xor-ed to create the packet's message.

The analysis shows that $O(n)$ packets that make to the receiver are enough for decoding, by allowing finding degree-one packets and xoring its content from all other packets that contain the same block (decreasing their degree by one).

What I haven't found in Luby's paper, or anywhere else, is the runtime complexity of the decoding. That is, what's the overall time spend on computing the original message.

A simple argument shows that $O(n^2)$ time is enough. Can we do better?


texts: Except for isomorphisms, the minimal DFA of a regular language is unique. However, is it possible that an equivalent NFA has less states than the minimal DFA? If so, what is the reasoning behind this? Due to the conversion of an NFA to DFA (which produces $2^Q$ states) it seems to me that a NFA can indeed have less states than a minimal DFA, but I'm not quite sure of this. Thanks in advance.


texts: Do all DFA's containing an "accepting path containing a cycle" accept infinite languages?

texts:
So I've seen this claim being made on different questions:

Do self-loops in DFA cause infinite languages?

I'd like to find formal proof for this.

I think I should also note that an "accepting path containing a cycle" is probably defined as a path in a graph so that the states in the DFA  are  nodes in the graph and there must be a cycle and at least one accepting state in that path.


texts: Finding a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$

texts:
I am trying to find a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$, but I can't seem to find one.

Definitions:
$$\begin{align*}
CF_{TM} &= \left\{ \langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is context-free} \right\} \\
A_{TM} &= \left\{ \langle M,w \rangle \mid \text{$M$ is a TM and $w \in L(M)$} \right\}
\end{align*}$$

AFAIK the mapping reduction of the regular (i.e., not the complimentary) language is as follows: $\langle M,w \rangle \in A_{TM}$ if and only if we can construct a language $L$ which is context-free in the sense that $L(F((\langle M,w \rangle)))$ is context-free.


texts: The requirement of the encoding to be prefix free results in large trees due to the tree having to be complete. Is there a threshold where fixed-length non-encoded storage of data would be more efficient than encoding the data?


texts: How can I write this simple function in mathematical notation?

texts:
POINTS_TABLE = [3, 5, 7, 1]

function score(answer) {
  result = 0
  for i in 0..4
    result += POINTS_TABLE[answer[i]]
  return result
}

answer = [1, 2, 1, 0]

s = score(answer)

The sum performed is 5 + 7 + 5 + 3 = 20. It uses the values from the input as the indexes to read from the POINTS_TABLE.

This is the style of the answer I'm trying to work out:
\begin{equation}
score(answer) = \sum_{i=1}POINTS\_TABLE_{answer_i}
\end{equation}


texts: What is a brief but complete explanation of a pure/dependent type system?

texts:
If something is simple, then it should be completely explainable with a few words. This can be done for the λ-calculus:

  The λ-calculus is a syntactical grammar (basically, a structure) with a reduction rule (which
  means a search/replace procedure is repeatedly applied to every occurrence of a specific pattern until no such pattern exists).

  Grammar:

Term = (Term Term) | (λ Var . Term) | Var

  Reduction rule:

((λ var body) term) -> SUBS(body,var,term)
    where `SUBS` replaces all occurrences of `var`
    by `term` in `body`, avoiding name capture.

  Examples:

(λ a . a)                             -> (λ a a)
((λ a . (λ b . (b a))) (λ x . x))     -> (λ b . (b (λ x x)))
((λ a . (a a)) (λ x . x))             -> (λ x . x)
((λ a . (λ b . ((b a) a))) (λ x . x)) -> (λ b . ((b (λ x . x)) (λ x . x)))
((λ x . (x x)) (λ x . (x x)))         -> never halts

While somewhat informal, one could argue this is informative enough for a normal human to understand the λ-calculus as a whole - and it takes 22 lines of markdown. I'm trying to understand pure/dependent type systems as used by Idris/Agda and similar projects, but the briefer explanation I could find was Simply Easy - a great paper, but that seems to assume a lot of previous knowledge (Haskell, inductive definitions) that I don't have. I think something briefer, less rich could eliminate some of those barriers. Thus,

Is it possible to give a brief, complete explanation of pure/dependent type systems, in the same format I presented the λ-calculus above?


texts: How generate regular expression on the alphabet {a,b}?

texts: How can I write a regular expression that denotes language on the alphabet {a,b}  of the strings that do not present "b" consecutive and the total number of "a" is multiple of three?.


texts: MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?

texts:
What is the complexity of $\text{MIN-2-XOR-SAT}$ and $\text{MAX-2-XOR-SAT}$?  Are they in P?  Are they NP-hard?

To formalize this more precisely, let

$$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i,$$

where $\mathbf{x} = (x_1,\dots,x_m)$ and each clause $C_i$ is of the form $(x_i \oplus x_j)$ or $(x_i \oplus \neg x_j)$.

The $\text{2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that satisfies $\Phi$.  This problem is in $P$, as it corresponds to a system of linear equations mod $2$.

The $\text{MAX-2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that maximizes the number of clauses that are satisfied.  The $\text{MIN-2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that minimizes the number of clauses that are satisfied.  What are the complexities of these problems?

Inspired by Is MIN or MAX-True-2-XOR-SAT NP-hard?


texts: Multiple inputs in lambda calculus (Confusing example)

texts:
In a programming class I take, we briefly (very briefly) touched lambda calculus. I think I have a pretty good grasp of the basics now, but one example given I just don't understand. Am I missing something or is the example possibly false?

$\lambda x.x \; (\lambda y.2*y) \; square \; 3$

The solution to this was $6$, because $\lambda x.x$ (the first function) is applied to $square$ (the first input) which just "disappears" and $\lambda y.2*y$ is applied to $3$, which gives us $6$:

$\lambda x.x \ (\lambda y.2*y) \ square \ 3 \implies (\lambda y.2*y) \ 3 \implies 2 * 3 \implies 6$

EDIT

Regardless of whether the "disappearance" of $square$ is correct, why would the first step be to apply $\lambda x.x$ to $square$ ? Instead of the whole expression, or just the part in parenthesis (which would, afaict, give the same result). I.e., what way of parenthesising is implied from the way it's written above?

/EDIT

The way I understand it, it should be either 18, because:

$\lambda x.x \; (\lambda y.2*y) \; square \; 3$ with parenthesis should be:

$(((\lambda x.x \; (\lambda y.2*y)) \; square) \; 3)$ which gives me:

$(((\lambda y.2*y) \; square) \; 3) \implies ((2*square) \; 3) \implies 2 * square(3) \implies 2 * 9 \implies 18$

or nothing at all, i.e. $((2*square) \; 3)$ doesn't make sense.

Another example that was given:

$(\lambda f.(\lambda x.f(f \; x))) \; square \; 3 \implies (\lambda x.square(square \;x)) \;3 \implies square(square \; 3) \implies square(9) \implies 81$

This second example seems clear to me, I'm just adding it to show something similar.

How would one properly solve $\lambda x.x \; (\lambda y.2*y) \; square \; 3$ ?


texts:
I have an edge-colored network, in which edges also  have a length, and I am considering the problem of determining the shortest Path between a pair of nodes, with the additional constraint that the number of colors of edges in a path should not exceed an integer $k$.

It corresponds to finding shortest Paths on a multimodal network, with the only restriction being a limitation in the number of changes of modes allowed (e.g. different bus lines, and no more than three changes of bus).

I am trying to determine the complexity of this problem.

I have found a line of research combining graph theory and formal languages theory [1], which is interested in the more general problem of paths constrained by the fact that the word formed by the labels of a path belongs to a certain formal language. Theorems state that:

The problem is in $P$ if the above language is context-free.
It is $NP$-hard for regular languages.

So alternatively, my question could be stated as follows:

Is a language over a finite alphabet, in which words can be of any length, but have to use a limited number $k$ of different letters, regular or is it context-free?
E.g. the language of words using at most four latin letters. "HELLO" is okay but "HELPS" is not. Is this regular or context-free?

I would appreciate any pointers to literature discussing the problem in either form (but would really prefer a purely graph-theoretic proof of NP-hardness or polynomial algorithm). Otherwise, I guess I will have to invest a few weeks learning about formal languages.

Thank you in advance. The help I have received so far in this forum is outstanding.

[1] Barrett, C. et al. 2000. Formal-language-constrained Path problems. SIAM journal of computing. Vol. 30, No. 3, pp 809-837.


texts:
I'm working on optimizing the structure of an optical meta device.
I have a randomly generated 2D matrix, where 0,1 represents the presence/absence of a hole.
Each structure manipulates light differently, thus giving rise to a unique spectrum.
The problem I wish to solve is to maximize the efficiency of this structure. Given the large size of the solution space ($2^{100}$ in this case), it isn't possible to simulate each structure. Is there any search method I could use to complete this optimization?
A general workflow would be:

Generate a random hole structure
Flip one or some bits (based on the optimization algorithm)
Compute the spectrum
Go back to step 2 and make a decision based on the previously computed spectrum.

Here's a link to a sample hole array.
Apologies for the vague statement of the problem.
The objective function to score a structure: Thank you D.W. for pointing this out. The problem is of course meaningless without an objective function. I'd initially omitted it in the question, so as to not make it irrelevant for this forum by adding too much physics.
The system has a transmission $(T)$ and a reflection $(R)$, so a good objective function would be:
$\mathcal{L} = min(T) - \alpha*max(R)$
Maximizing $\mathcal{L}$ would Maximize the Transmission while minimizing the reflection.
Based on the suggestions in the comments, I did try out a Genetic Algorithm Approach (basic algorithm given below)
for iterations:
    for batch_size:
        flip n bits in the structure randomly
        compute objective function

    structure = structure with the highest objective function value in the batch

However, though there is a slight increase in the Objective function initially, it saturates quickly and doesn't reach the expected values (Image below X-Axis - Iterations, Y-Axis - Objective Function Value).

I have tried multiple values of batch size, bitflips (n). Is there any alternate algorithm or any possible modification to the current algorithm?
Thanks in advance!


texts:
I am thinking of techniques that we can implement in order to avoid deadlocks in processes. While I am aware of some tactics, e.g. killing a process when we reach a deadlock, or using spooling, would there be any other viable solutions?
For example, can we adjust a process to be executed if it is urgent, and has higher priority for execution, or maybe execute a process which asks for the smallest amount of resources? Or even, depending on the resource, we remove it from a process which has reached a deadlock and then re-use it by giving it again to the processes?


texts: How to count stores in cache analysis of matrix multiplication

texts:
I'm trying to understand cache misses/iter and came across this that I couldn't understand or reason out.

For ijk iteration, my slides say that there are 2 loads and 0 stores.

for (i=0; i<n; i++) {
  for (j=0; j<n; j++) {
   sum = 0.0;
   for (k=0; k<n; k++)
     sum += a[i][k] * b[k][j];
   c[i][j] = sum;
  }
}

Similarly, for kij iteration, my slides say that there are 2 loads and 1 store.

for (k=0; k<n; k++) {
 for (i=0; i<n; i++) {
  r = a[i][k];
  for (j=0; j<n; j++)
   c[i][j] += r * b[k][j];
 }
}

And for jki iteration, my slides say that there are 2 loads and 1 store.

for (j=0; j<n; j++) {
 for (k=0; k<n; k++) {
   r = b[k][j];
   for (i=0; i<n; i++)
    c[i][j] += a[i][k] * r;
 }
}

I believe the loads are counted in each case when data is referred to by calling arr[x][x] on the right hand side of the arithmetic evaluation, which would make two in each case. But how are the stores counted?


texts: is reducing to normal form simply applying beta-reduction?

texts:
See example below:

reduce to normal form:

(λ c . (λ a . (λ d . (λ h . (h (d (a (a (λ z y . y))) (d (a (a (λ f x . x))) (a (a (a (λ z x . x)))))) (h (a (a (λ z y . y))) (a (a (a (λ z x . x))))))) (λ n m . n (d m) (λ z y . y))) (λ n m . n a m)) (λ n z . c (n z) z)) (λ z g x . z (g x))

Wikipedia says that to be in normal form: all reductions that can be applied have been).

I used these two calcualtors to try and get the correct reduction:
http://lambda.jimpryor.net/code/lambda_evaluator/
http://lambda.jimpryor.net/code/lambda_evaluator/

both return:
λz x.z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z(z x)))))))))))))))))))))))))))))))))))))))))

Can I get to this answer by only using beta-reduction? This is the only reduction I am currently trying to understand but from this example there are two more:
https://stackoverflow.com/questions/34140819/lambda-calculus-reduction-steps


texts: 2-Approximation algorithm for for messages across a cyclic network

texts:
Question
There are $n$ computers arranged in a cycle ($1,2,3..,n,1$), with undirected edges between adjacent computers. There are $m$ messages that need to be delivered. Message $i$ ($1 \le i \le m$) has to be sent from computer $s_i$ to computer $t_i$. There are two ways to deliver a message $i$: clockwise from $s_i$ to $t_i$ or anti-clockwise from $s_i$ to $t_i$. Aim is to send all messages in such a way that the number of messages going through the most frequently used edge is minimized. We need to devise a $2$-Approximation algorithm for the same.
Example
Let $n=4$. Let $m=2$. And let $s_1=1,t_1=4$ and $s_2=2,t_2=3$. Then if we send message $1$ in the following way: $1 \to 2 \to 3 \to 4$ and message $2$ as: $2 \to 3$. The most frequently edge used is $2 \to 3$, through which $2$ messages go. We can do better than this.
Message $1$:  $1 \to 4$ and delivery of message $2$ remains same $2 \to 3$. Then both the edges are most frequently used. But only $1$ message goes through most frequently used edges.
My approach 1
For every message with probability $\frac{1}{2}$ send it in clockwise direction and with $\frac{1}{2}$ in anti-clockwise direction.
But this gives a bad performance, which can be seen with the help of the following example:
$n=10000$, $m=200$ and $s_i = i,t_i=i+1$ for $1 \le i \le 200$. Then the optimal answer is $1$ (ie. every edge has at most $1$ message going through it). Which can be achieved by sending message $i$ as $i \to (i+1)$.
Also this is the only way to achieve the optimal. If anyone of the messages were sent in the other direction the answer increases. For eg. if $x$ of the $200$ messages were sent in other direction, all these $x$ would use say edge $800 \to 801$. So the answer would be at least $x$. Thus in this case the random solution picks the optimal arrangement with only probability $\frac{1}{2^{200}}$, which is very less and for other arrangements answer gets bigger.
My approach 2
I turned towards greedy. Where for message $i$ we send it in the direction where it will travel through lesser number of edges, ie. we send it along the shorter route. Then I argued as below
(I consider $n$ odd for now, and also don't consider some other corner cases)
For an arbitrary input $n$, $m$ (and the respective source and sinks) let the optimal be $p$ (that is $p$ is the number of messages going through the most frequent used edge), then the optimal arrangement cannot have more than $2p$ messages for which longer routes were chosen. Reason: longer routes have at least $\frac{n+1}{2}$ contiguous edges, for example for $n=7$, if I list all thecontiguous subsets of size $\frac{n+1}{2}$ (the possibilities of longer route)
$$
1,2,3,4 \\
3,4,5,6 \\
4,5,6,7 \\
6,7,1,2 \\
7,1,2,3 \\
$$
and lets say $p=1$. Then as first two subsets (nearly the half) have a common element $4$, and so do the last three subsets (again nearly the half) have common element $7$ (this is true for arbitrary odd $n$).
There can be a case where (in the optimal arrangement) $p$ of the longer routes lie in first half of subsets and another $p$ of longer routes in the second half of subsets. But if more than $2p$ are there. There would be at least $p+1$ in a single half of subsets, making the answer $p+1$ which is a contradiction.
And as changing direction of a message can at worst increase the answer by $1$. The greedy should have answer $\le 3p$ (change all $2p$ longer routes to short, to get to what greedy outputs).
But I seem to be stuck beyond this. As this gives approximation factor of $3$ (I did not consider $n$ is even case, as I think if odd case is handled it will be just about the corner case of source and sink being at exactly $\frac{n}{2}$ distance).
Maybe in my reasoning I overestimated somewhere.
I had also tried tried to obtain bounds using weak duality by expressing problem as LP relaxation. Assuming my working was correct what I could get is $1\le$ optimal. Which is trivially true.
PS: I would highly appreciate hints only.


texts:
I have a question

  Given a 16-bit register A holding a number in 2’s complement form, use a
   single gate (e.g., AND, OR,
  XOR, NAND, NOR, NOT) with an arbitrary number of inputs to implement a
  circuit that produces an
  output 1 if the number is divisible by 16, and an output 0 otherwise. The
 bits are labelled A15, A14, ..., A0.

I'm confused at how this answer is expected because the question is only 2 marks my answer was that it would be a single XOR gate with inputs a0-a15 - would this be correct and why?


texts: What is the use of finding minimum number of straight lines to cover a set of points?

texts:
There is that popular problem [1] [2] in the computer science that is finding minimum number of straight lines that covers a given set of points in 2D.

Even though I have scanned many papers, none of them has a clear motivation for the problem.

What is the use of solving this problem? Is there a paper that explains this?


texts: how many boolean functions exist that satisfy the condition

texts:
How many boolean functions exist that satisfy the following condition?
$$\neg f(x_1,x_2,x_3,....,x_n) = f(\neg x_1, \neg x_2,...,\neg x_n)$$


texts: A doubt on converting NOT gate to CNF formula

texts:
For a NOT gate if $x_1$ is input and $x_2$ is the corresponding output, I see the equivalent CNF (conjunctive normal form) is $(x_1 \lor x_2) \land (\overline x_1 \lor \overline x_2)$.

My expectations was that the CNF should not include $x_2$ as it is the output of the gate. I was rather hoping the formula to be of a form $x_2=F(x_1, b_1, b_2, ...)$ where $b_1$, $b_2$, .. are the boolean constants such that when $x_1$ is zero, the $F(.,.,..)$ would yield true just like the NOT gate.

Can anyone help me understand, how come this CNF including $x_2$ is equivalent to a NOT gate. How to draw a truth table for this CNF form as in what value to assign for $x_2$!


texts:
Let $L = \{\lt M\gt | M$ is a $TM, L(M) = \{1^n0^n | n\ge0\}\}$.
Create a reduction from $A_{TM}$ (acceptance problem) to $L$. Is $L$ not decidable?
 But isn't $L$ decidable since it is possible to make a CFG (or PDA) of that language. And if I can make a reduction, $L$ would become not decidable because of $A_{TM}$.


texts: Determine if there is a subset of the given set with sum divisible by a given integer

texts:
I've been given a question to solve:

Given a set of non-negative distinct integers, and a value $m$, determine if there is a subset of the given set with sum divisible by $m$.

For this question the answer is here
I don't understand the part after if DP[j]==True
what is actually the intuition behind this code. Please explain in detail.


texts: Constructing a pushdown automaton that accepts L*

texts:
Would appreciate if you could take a look at what I did and help me finish it.

  Given a pushdown automaton that accepts a language $L$ by final state, construct a pushdown automaton that accepts $L^*$. Use a "double bottom" if need be.

My attempt:

Given  $M = (Q,\Sigma,Γ,\delta,q_0,⊥,∅)$, we'll add a double bottom by altering the function: $\delta' := \delta'(q_0',\epsilon, ⊥')={(q_0, ⊥⊥)}$, so M' is basically $M' = (Q\cup{q_0',q_f},\Sigma,Γ∪{⊥'},\delta',q_0',⊥',{q_f})$. The accepting state is reached by $\forall q \in Q\colon \delta' (q,\epsilon,⊥')={(q_f,⊥')}$.

How do I finish it so that it accepts $L^*$?


texts: In RSA, must $p$ and $q$ have the same number of bits?

texts: Is it necessary to take the same bit size of "p" and "q" in case of RSA algorithm? i had read that  bitsize of p and q must be same. BUT after calculating, i found that bit size could be different also. But time complexity will increase. Can anyone help me?


texts: How to find optimal sweet spot for time-space trade-off?

texts:
If an algorithm can solve a problem in X iterations using Y bytes of space, then another algorithm that solves it in less bytes than Y, will usually end up needing to do it in more iterations (or time) than X.
One can keep increasing the space/memory to reduce the cycles or cpu time, but will eventually get cursed by something, I guess cost of purchasing all that memory.
On the other hand, one may go the opposite direction and suffer increase CPU time.
In other words, on one end we face time (more cpu cycles means more waiting), and on the opposite end we face the cost of space (e.g. RAM price).
This means that the time-space can be seen as a possibility convex-like curve if we view it as the time-space/cost perspective.  So I guess the sweet-spot is the middle hanging point under convex's belly.
My question is: what is done in this regard to make this chart more convex-like?  Because as soon as we do it we can know sweetpoint in the trade offs option.


texts: Undecidability: writing a symbol on Turing Machine's tape

texts:
I wonder to know if given a Machine $M$, a string $x$ and a symbol $\phi$, would $M$ ever write $\phi$ ?

My approach

Maybe i can show if the problem is undecidable by contradiction using $M$ to prove $\operatorname{HALTING PROBLEM}$, but i'm stuck here. Any hints ?


texts: How to draw NPDA for words whose number of b's is strictly more than that of a's but strictly less than twice the amount

texts:
I know that CFG for $$ \{a^{m}b^{n}\mid m\leq n\leq 2m \}$$ is
$$ S\rightarrow ab/abb/aSb/aSbb $$ but I am not able to tweak  it in such a way that it is strictly in between m and 2m and not equal to any of m or 2m.
I want to draw PDA for the same.

For drawing the PDA what I did was to push non-deterministically  1 a and 2a's and popping them out for b one by one. How should I handle the edge case that it always doesn't push 1 a or not always 2 a's?


texts:
I'm trying to reduce this example from Circuit-sat to 3-Sat, but I got stuck. Can some one give a brief explanation step by step?

Tree: schema

My attempt:


texts: Does every infinite context free language contain an infinite regular subset?

texts: Can someone explain to me if this is true or not?


texts: Do poly-computable differentiable functions on [0,1] with bounded number of turning points have poly-time computable inverse?

texts:
Given a polynomially computable continuous function which is a composite of m strictly monotone functions, can we guarantee the existence of polynomially computable inverse?
The function I have in mind is a rational function and all the coefficients (in the numerator and denominator) are positive integers but are unknown. I realize that for strictly monotone functions, as long as it is honest (arbitrarily long fractions don't get mapped to short ones - are rational functions honest?) a binary search algorithm will find the inverse. But in case of existence of m maxima and minima, how to devise an appropriate algorithm that won't get stuck?
We are of course restricting the function to $\mathbb{Q}\to \mathbb{Q}$ and for a given $q\in \mathbb{Q}$, for our purposes, it will suffice to have a polynomial time algorithm to find the minimum (maximum) approximate rational pre-image, where the error $\epsilon$ can be made arbitrarily small in time polynomial in $\epsilon^{-1}$.


texts: Floating point number fractions excercise

texts:
During my preparation for an exam, I've come across an exercise that was focused on precision calculation with floating point numbers. It goes like this:

  Consider the expression : $$\frac{1}{1-x}-\frac{1}{1+x}, x\neq \pm1$$
  For what range of values $x$ is it difficult to compute the expression accurately in foating-point arithmetic? Give a re-arrangement of the terms such that, for the range of values from part (a), the computation is more accurate in foating-point arithmetic.

I have some basics covered on floating point number systems, so I've tried to set $\pm x=0.9999...$, with a different number of decimal digits. The calculations are indeed more and more imprecise, however I don't know if this is the only problematic 'range'. Also, I have no idea how to transform this expression to be more accurate. I have tried $\frac{2x}{1-x^{2}}$ and $e^{\ln{2x}-\ln(1-x^{2})}$, but the results were pretty much the same.

Thanks for help!


texts: Why merge into the larger tree in union by rank

texts: When we do union by rank we merge the smaller tree into the larger tree. I dont understand why we do this exactly?


texts: Proving that context-free languages are closed under inserting symbols

texts:
This is a theoretical computer science question, regarding the proof of whether or not context-free languages are closed under an operation.  This means basically that any context-free language which undergoes this operation would still be context-free.

  For a language $A$ which is a subset $\Sigma^*$, define the language $A_+$ as

  $\qquad\displaystyle A_+ = \{xyz | y\in \Sigma \wedge xz \in A\}$.

  Prove that the set of context-free languages is closed under the $+$ operator.

So $A_+$ contains all strings that can be obtained by inserting one symbol into a string in $A$.
Show that the class of context-free languages is closed under the operation $+$ (i.e.,     show that
if $A$ is context free, then $A_+$ is also context free).

Note that this is not a homework question.  Examples of closure proofs are sparse online and in my textbook.

First, let's think about the different ways to prove closure of CFLs:

Constructing a "template" Push Down Automata that can incorporate any other Push Down Automata and add on a part to the beginning, middle, or end of the PDA and still be able to accept the language accepted by the original CFL, with the new operation on it.  Basically, if for any given PDA P, if a PDA P' can be created which accepts the language of P with the new operation (in our case, the "+" operator) performed on it, then that operation must be under closure.

Solving the problem in this manner is quite simple to think about.  Imagine a PDA P which accepts strings from the CFL L.  In application to our problem, this would be a PDA which can successfully read in the string 'xz', where x and z are simply any string conforming to our alphabet.  The PDA P' would similarly have the ability to read xz, but each state of the PDA could have an additional self loop which reads the character in the string y.

I have selected the answer which I find to be most appropriate for this question.  It simply involves using the "tempate PDA" strategy which I outline above; however, my construction did not achieve the goals of the new language (think about why before looking at the answer below).


texts: Guarantees on computing $a+x(b-a)$ in floating point

texts:
I want to implement the function $f(x,a,b) = a + x(b-a)$ where all the inputs are floating point (doubles, say), such that (a) $f(0,a,b)=a$ exactly; (b) $f(1,a,b)=b$ exactly; (c) $f(x,a,b) \le f(y,a,b)$ whenever $x \le y$; and preferably (d) it is accurate (correct up to rounding) for $0 \le x \le 1$.

Implementing $f(x,a,b)=a+x(b-a)$ directly does not work because for example $f(1.0,-1.0,\operatorname{prev}(1.0)) = 1.0$ (where $\operatorname{prev}(a)$ is the floating point number before $a$). And $f(x,a,b)=b-(1-x)(b-a)$ has the same issue.

Now $$f(x,a,b) = (1-x)(a+x(b-a))+x(b-(1-x)(b-a))$$ has the first two properties.

Does it have property (c)?
How accurate is it?
Is there a more performant way to do this?


texts: How does $n^c \lg n, 0<c<1$ compare to other common time complexities

texts:
Between what two common time complexities would you place $n^c lg n, 0<c<1$?

The following table illustrates the common time complexities.
Source: wikipedia


texts: Proving that a language defined by a regular expression is equivalent to a right linear grammar

texts:
After thinking for a bit, I am not able to prove a double inclusion proof for the following problem. It seems very interesting to me.
Consider the regular expression $r= ((1(00)^∗1 + 0)1)^∗$ and the right-linear grammar $G= (\{S,A\},\{0,1\},S,P)$, where $P$ consists of the following rules:

$S\rightarrow 1A|01S|\lambda$
$A\rightarrow 00A|11S$

Prove that $L(G)\subseteq L(r)$ and vice versa.
In general, how exactly do I prove that a regular grammar describes the same language as a regular expression?


texts:
Can someone tell me what binary NP-Hard exactly means.
My understanding was that if the problem is encoded in binary and if the problem is binary NP-Hard, its complexity of solving is NP-Hard. Is this the correct interpretation?

I also wanted to know, if binary NP-Hard also says something about Strong or Weak NP-Completeness of the problem.


texts: Phrase generators for use with testing grammars that don't use a seed

texts:
In helping someone understand phrase generators for use with testing grammars, think compiler test cases, I noted that I have never found a phrase generator that is knowledgeable of the grammar, and is deterministic. The phrase generators I am talking about rely on the grammar of the language as input so that the user does not have to recreate the rules for the grammar into a format acceptable for the tool. The tool must accept a BNF grammar; I don't mind if the grammar has to be factored some for the tool before input. Tools that rely on a seed or generate a random seed are what I want to avoid.

I am aware that one can use PROLOG to generate a parser and then run a query that outputs a set of results that are phrases used for testing. I also know that it is not uncommon for these result sets to have 10**15 answers for basic cases of a grammar like C++.

Does anyone know of such tools? They can be commercial or open-source as I don't plan on using it, I have my own, I just want to verify my knowledge.

EDIT

The tool must encompass sematic knowledge of the compiler. In other words the phrases must be able to be compiled by a compiler, not just pass the syntactic rules.

EDIT

I agree that the comments and answers regarding deterministic are correct and I my use of the word here is not correct.

What I am looking for is a tool that not only takes in a BNF grammar and can use it "as is" which would mean for a grammar like C++ a basic result sets with 10**30 items. That is not an accurate number but a realistic one based on a phrase generator I have that can report the number of results before generating the results. Since that size of a result set is impractical, I have given the tool the ability to enhance the grammar with constraints, thinking tree pruning. This allows one to generate phrases for one particular branch of the grammar, and also prune and limit the sub-braches and number of recursion over those branches. Even with the constraints each result item is a valid C++ file for use as input to a C++ compiler.

I have a proof of concept of this already, but the difference between a proof of concept and useful tool is a lot of work. So while a seed can be reused and create deterministic results, it does not allow the user to determine the conditions.


texts: Find $n'th$ perfect number , where perfect number is a positive integer whose sum of digits is $10$

texts:
For example $46$ is a perfect number , since $4+6=10$ . If $n=1$ , answer is $19$. If $n=2$ , answer is $28$. If $n=3$ , answer is $37$ and so on .We need to make a program which takes $n$  and outputs $n'th$ perfect number.

How to solve this problem for large $n$ , for example $n$ close to $10^{18}$ ? we can't use brute force method since input can be so large .Can we solve it using DP or binary search ?

Source of the problem : Perfect Number

Note: In given problem statement (in link) $n$ is not large and thus can be solved using brute force.But i am curious to solve it for large $n$.


texts:
Assume $P=PSPACE$. Then would it be possible to design cryptographic protocols based that is easy to compute from $PSPACE$ but hard to invert from something higher up in hierarchy?

A function $f: \{0, 1\}^*→ \{0, 1\}^*$ is one-way if $f$ can be computed by a polynomial time algorithm, but for every randomized algorithm $A$ that runs in time
polynomial in $n=|x|$, every polynomial $p(n)$, and all sufficiently large $n$

$$Pr[ f( A( f(x) ) ) = f(x) ] < \frac{1}{p(n)}$$

where the probability is over the choice of $x$ from the uniform distribution on ${0, 1}^n$, and the randomness of $A$.

Is replacing polynomial time by $PSPACE$, randomized by some other notion possible in above definition if $P=PSPACE$?


texts: What is the fastest algorithm to solve $k$-path problem?

texts:
$k$-Path problem

The problem: Given a graph $G$ with $n$ vertices and $m$ edges, does there exist a path of length $k$ in the graph?

The trivial algorithm to solve is in $O^*(n^k)$ time using dynamic programming. ($^*$ hides the polynomial factor.)

Question: What is the fastest algorithm for the $k$-Path problem?


texts: If a graph has $15$ vertices, one with degree $8$, $6$ with degree $6$, $8$ with degree $4$, is it a planar graph?

texts:
The question is as above.
I want to prove that there exists a $K_5$ as a subgraph, so this graph is not a planar graph. But I failed.
If you can help me, I will be very appreciative.


texts: Operational Semantics - Include SKIP, SEQUENCE and IF?

texts:
I'm writing a paper for a programming languages workshop in which I have to describe the semantics of a new optimization for Java using Operational Semantics, small step style.

I have never used Operational Semantics before so I'm doubtful as whether to include in the paper some rules I'm using that are rather... let's say "common", such as the SKIP and the IF rules.

My programmer mindset tells me that perhaps there is some kind of "repository" of rules I can refer to by citing a paper or saying something "the common SKIP and the common IF rules you all know" in the paper

So the question is: should I include all rules in my paper or there is a way a can refer to them by citing, etc.?


texts: What is total work of managing the dynamic array and why is it the same as for fixed array - O(n)

texts:
I'm reading the chapter on dynamic arrays in The Algorithm Design Manual book. Here is the excerpt from the book:

  Actually, we can efficiently enlarge arrays as we need them, through
  the miracle of dynamic arrays. Suppose we start with an array of size
  1, and double its size from m to 2m each time we run out of space.
  This doubling process involves allocating a new contiguous array of
  size 2m, copying the contents of the old array to the lower half of
  the new one, and returning the space used by the old array to the
  storage allocation system. The apparent waste in this procedure
  involves the recopying of the old contents on each expansion. How many
  times might an element have to be recopied after a total of n
  insertions? Well, the first inserted element will have been recopied
  when the array expands after the first, second, fourth, eighth, . . .
  insertions. It will take log2 n doublings until the array gets to have
  n positions. However, most elements do not suffer much upheaval.

  Indeed, the (n/2 + 1)st through nth elements will move at most once
  and might never have to move at all. If half the elements move once, a
  quarter of the elements twice, and so on, the total number of
  movements M is given by

  Thus, each of the n elements move only two times on average, and the
  total work of managing the dynamic array is the same O(n) as it would
  have been if a single array of sufficient size had been allocated in
  advance!

  The primary thing lost using dynamic arrays is the guarantee that each
  array access takes constant time in the worst case. Now all the
  queries will be fast, except for those relatively few queries
  triggering array doubling. What we get instead is a promise that the
  nth array access will be completed quickly enough that the total
  effort expended so far will still be O(n). Such amortized guarantees
  arise frequently in the analysis of data structures.]1

I don't understand why (n/2 + 1)st through nth will move at most once and might never have to move at all and total work of managing the dynamic array. Can someone please explain?

Also, why is the guarantee that each array access takes constant time in the worst case is lost with dynamic arrays?


texts:
Find a function that bounds from above and below (asymptotic) the rank of the root r in an AVL tree,
i.e. find a function $f(n)$ so there exists a constant $c>0$ that for every AVL tree with $n$ nodes so
$c * f(n)\le rank(r)\le n-c*f(n) $.

$rank(r)$ gets his maximum value when his sub-left tree contains maximal number of nodes and because it's an AVL tree, for tree with height $h$ the sub left tree will be with height of $h-1$ and the number of nodes will be maximal when the sub tree is a full tree with $2^{h-2}-1$ nodes hence we get:
$rank(r)\leq 2^{h-2}-1+1=2^{h-2}$

On the other hand, $rank(r)$ gets his minimal value when his sub left tree contains a minimal number of nodes and it happens when the sub left tree is a fibonacci tree with height of $h-2$, therefore
  $rank(r) \geq \phi ^{h-2}+1$.

Now I need to find f as a function of the number of nodes $n$ and not the height $h$.
Am I in the right direction?
  Would apricciate any help how to continue, Thanks.


texts: Find all non-isomorphic graphs with a particular degree sequence

texts:
I have a degree sequence and I want to generate all non-isomorphic graphs with that degree sequence, as fast as possible.

The only way I found is generating the first graph using the Havel-Hakimi algorithm and then get other graphs by permuting all pairs of edges and trying to use an edge switching operation (E={{v1,v2},{v3,v4}}, E'= {{v1,v3},{v2,v4}}; this does not change vertice degree).

Are there any faster algorithms?


texts: Operating Systems Qualifying Exam Visual Study Aids

texts:
I have read the Operating System Concepts book, watched a lot of videos on YouTube, practiced with past qualifying exam questions and several exams from other CS departments around the world.

Although I feel better about going into the exam, I have been searching for:

Large diagram that puts most of OS concepts in perspective
Video that shows the lifecycle of a process, etc…

I can undersand full-well why such a digram may not exist. It is possible to propose a case of a concept then diagram its "life-cycle"... but I havent found one. Has anyone see anything like this? I am a very visual person and things make more sense to me when I can express them in a diagram.

At this point I feel that I will draw the diagram myself, and this way I can test my knowledge and also share it with others. But before I do that, I want to make sure I am not re-inventing the wheel.

If you are going to down-vote my question, please leave a comment also.


texts:
There is a following Turing machine. I want to understand what it is doing :

I tried running it on input 100, 10000. Both these strings are accepted whereas 10,1000 are rejected
That leads to a good guess that it's accepting the string's with 1 followed by 0's where number of
0's = power of 2. But I can't prove it or deduce it from looking at the state diagram of it.
Any insights into it ?


texts: Do not understand why log n = O(n^c) (for any c>0)

texts:
Can anyone help me understand this equation?

  $\log (n) = O(n^c)$    (for any $c>0$)

Does it mean that $O(\log (n)) < O(n^c)$ (for any $c>0$)?

Added:

Please also prove that $\log (n) = O(n^c)$ is true.


texts: Algorithm: given very large file of strings, find lines containing substring

texts:
I'm not sure if cs.stackexchange.com is correct place to ask this question but it looks like most relevant.

On the job interview I was asked a question: lets say we have a very large file, containing a lot of lines with strings. And lets say that one line is a "document". We are building service which takes some string as input and returns numbers of documents containing this string or substring. Which approach would you use?

And I'm stuck with event trying to find a way to do it. Obviously we can just go through the file with every query and count lines containing substring and it will take O(n) time. But there should be more elegant and fast way to do it, right? I have no CS grad, so my knowledge about algorithms and data structures are not systematic.

My intuition says that it should some very basic question (like knackpack problem, for example) and I just don't know right data structure and algorithm to handle it.

It looks like suffix tree could help somehow but I can't find a way - how? Or, maybe, there is some another approach?


texts: Method provided by component may need to be implemented, What does this mean?

texts:
I can't wrap my head around this statement:

  One common drawback of using composition instead of inheritance is that methods being provided by individual components may have to be implemented in the derived type, even if they are only forwarding methods

It's from here.


texts:
Which of the following cache designer guidelines are generally valid?

The shorter the memory latency, the smaller the cache block
The shorter the memory latency, the larger the cache block
The higher the memory bandwidth, the smaller the cache block
The higher the memory bandwidth, the larger the cache block

As per my understanding, 4 stands valid since larger memory bandwidth leads to a large cache block size. However what is the relation between cache block and latency?


texts: Why are there so many programming languages?

texts:
I'm pretty fluent in C/C++, and can make my way around the various scripting languages (awk/sed/perl). I've started using python a lot more because it combines some of the nifty aspects of C++ with the scripting capabilities of awk/sed/perl.

But why are there so many different programming languages ? I'm guessing all these languages can do the same things, so why not just stick to one language and use that for programming computers ? In particular, is there any reason I should know a functional language as a computer programmer ?

Some related reading:

Why new programming languages succeed -- or fail ?
is there still research to be done in programming languages?


texts:
Why is $P^{NP}\not\subseteq NP$ possible? After all we have a $P$ machine which uses an $NP$ oracle and since $P\subseteq NP$ why cannot the $P$ machine with $NP$ oracle just be replaced by an $NP$ machine?

Similarly why is not the case $P^{coNP}\subseteq coNP$?


texts:
I have a directed acyclic graph with positive edge weights. It is constantly changing in that nodes are deleted and added. For each change, I need to find the $k$ shortest paths.

My current approach is that I plan to run Eppstein's algorithm for each change, but I'd like to be able to reuse some of the calculations I've done in previous versions of the graph.

What is the fastest algorithm for this problem, considering it will run over multiple graph changes?


texts:
What would be the complexity of the following recurrence?

$$T(n) = 2T(n-1)$$


texts:
I am a CS undergrad and a huge enthusiast of pure math. I have been doing competitive programming and proofs for a while. My ambition is to become an academic in theoretical computer science. The problem I face, like any math enthusiast, is that academia pathway jobs are not reliable in terms of funding. So, I thought of getting an alternative job besides my academic career.

First, I have been looking for jobs in which I could utilize my mathematical curiosity. Second, As I am an Undergrad, I need a pathway whose beginning is accessible for me to gain money. Third, I live in the Middle-East. So R&D departments or technical consultancy firms in my region are not promising. So, I thought of working online.

After a little-bit of research, I guessed cryptocurrency mining is my best investment. It could be done online, requires mathematical skills, and funded.

I am well aware that my job request is nearly in-achievable to find. I am not asking to suggest me a magic solution that would give me everything. I am just seeking advice and consulting my community.

You could for instance advice me, (1) What academics do to gain more additional money, (2) What accessible career pathways I could gain money from, whose future is promising for a math enthusiast?, (3) What are the best opportunities to achieve something of a value in my CV, Even if it is not payed?

However, Feel free to give me any advice you believe is helpful.

Sincerely,