texts: A Turing machine going to the right by the first $2 |w|$ steps

texts:
A single-tape Turing machine $M$ has the property that, for every input $w$, during the first $2 |w|$ steps, the head of $M$ moves only right (it does not move left nor stays in place); the machine is also allowed to halt at any moment during these first $2|w|$ steps.
Prove that the language of $M$ is in $DTIME(n)$.

Perhaps I don't understand the problem because I don't know how to start. My intuition is following:

$L$ reconized by $M$ is $= K \cup M$ where $K$ is a set of such words $s$ that $|s| < |w|$. $M \cap K = \emptyset$.

We can consider two situation:

1) $M$ stops before $2|w|$ steps. It means that such word $w$ can be represented by regular expression. Therefore, such words can be accepted/rejected in $DTIME$.

2) $M$ stpes $2|w|$ to the right (or more) and now it can come back to the beginning. But, if machine is able to reach $2|w|$ steps without memory it means that $M$ can compute steps in any way. It cannot be "solved" using a tape- the machine cannot move left so the tape is useless. So, the information must be encoded in states. But, number of states is finite. So, let $|Q| = n$.

Then, there is limited number of such words that cannot be recognized using a deterministic automata.  The limited language can be recognized in $DTIME$. Other words can be recognized by deterministic automata.

It is my idea. I am not sure if is ok.

1) Is it?

2) Probably there is a better (one-sentence) solution. Please say me.


texts: In fast multiplier circuits, what is the difference between a Counter and a Compressor?

texts:
When working on fast parallel multiplier circuit designs, like Wallace tree multipliers or Dada tree multipliers I found many papers and books refer to different components used in the tree to reduce the partial products called things like (4:2) compressor, or (7,3) counter or (7:3) compressor.
My question is :

  "What is the difference between a (7:3) compressor and a (7,3) counter?"

  What makes us to call it a compressor rather than a counter? is there any rule?


texts: How does derandomization of 3SAT work via conditional expectations?

texts:
Given a single SAT clause with its 3 literals coming from 3 different variables it is obvious that  a random assignment of values will satisfy it with probability 7/8

But I do not understand how from the above argument it follows that given a $m$ clause SAT instance the probability of satisfying at least $7/8 - 1/2m$ fraction of the clauses is at least $1/poly(m)$ ?

[..firstly even in a single clause case its not clear how the 7/8 result can hold if variables are repeated - and in the multi-clause case there will now be correlations across clauses - and hence its hardly clear to me as to what is happening!..]

I believe there is some sort of a Markov inequality going on but I can't see it.

Now apparently one can derandomize this using "conditional expectation". (vaguely I understand that it is some way of estimating what is the chance of satisfying the formula when randomizing over a subset of the variables while keeping  the others' values fixed and then probably changing the subset in every round) This is totally unfamiliar to me as to how the above probabilistic argument can be converted into a deterministic one so as to ensure finding of an assignment of values to variables such that always at least 7/8 of the clauses are satisfied.

[..apparently the above can also be thought via "3-wise independent sample space" - if someone can help understand that then that would be great!..]


texts: Can voice biometrics, (specifically voice recognition) application be used at windows logon screen?

texts:
I'm planning to develop an application in C# programming language for user authentication.

Target platform = Newer Windows versions such as Windows 8/10.

Your kind answers will be much appreciated. Cheers!


texts: Theoretical machines which are more powerful than Turing machines

texts: Are there any theoretical machines which exceed Turing machines capability in at least some areas?


texts: Equivalence between a TM and a changing TM

texts:
Let a changing TM be a TM which is not able to write the same symbol which is being read.
Formal:  $M^*=(Q,\Sigma,\Gamma,\delta,q_{accept},q_{reject})$,$\delta(q,a)=(q^*,a^*,c),a \neq a^*$ with  $q,q^* \in Q, a,a^* \in \Gamma, c \in \{R,L\}$ .
Now I need to proof that a changing TM is equivalent to a normal TM.

My guess was to create a multi-tape TM which is able to simulate the changing TM(and therefore a TM is equivalt to a changing TM, since every multi Tape TM has equivalent single tape TM), but I am unnable to finish(write it formal and unformal down).


texts: Introduction to bounded model checking that describes model generation

texts:
Most of the tutorials I have found on model checking and bounded model checking start with, the model is given as a Kripke Structure M = (S,I,T,L) where S is a set of states, I is a set of initial states, T is a transition relation, and L is a labeling function.  Model checking takes a property P and tries to determine if P is true in the model M.

The algorithms for model checking (and bounded model checking) provided for a given Kripke structure are very understandable, and are all quite neat.  For example,

An Analysis of SAT-based Model Checking Techniques in an Industrial Environment

and the survey by Prasad et all 2005, are both very readable and understandable.

Now, suppose one wants to take a program and use model checking to determine if the program is correct.  As far as I can tell, the hard part is determining a suitable model of the program.  I am trying to figure out, for example, how CBMC derives a formula for a plain SAT solver since this would involve constructing a model and then a CNF formula for plain SAT such that if the formula is true then there is a counter example to the predicate.  I think they use bit-vector logic, whatever that means.

I have glanced through:

CBMC (C Bounded Model Checker)

Bit-Vectors in Decision Procedures An Algorithmic Point of View

Slides for CBMC: Bounded Model Checking for ANSI-C

These are focused on how a tool works, and lack some of the details I am looking for.  I'm curious if there are any more tutorialish writeups on how to build a SAT based model checking tool, and discuss how to develop the model and whether to use plain SAT of SMT solver.

Alternatively, if someone could point me in the direction of producing a model, given a property and a program written in a very simple language with say a single type: 32bit-Integers, functions, assignments, if-then, if-then-else, and optionally while-loops, that would output a formula for a SAT or SMT solver such that the formula is satisfiable iff the property is not true of the program, then I would also be so grateful.


texts: Should Expectation Maximization take into account the Naive Bayes' independence assumption?

texts:
Should the independence assumption on which the Naive Bayes (NB) classifier is based, be taken into account when applying Expectation Maximization(EM) to infer missing values?

The Naive Bayes classifier assumes that all attributes are independent given the class variable.
Normally, the given structure of a Bayesian Network would be exploited by the EM algrithm. However, the NB classifier still performs well enough when the assumption is not met. So it is entirely plausible to have a dataset, in which the assumption does not (entirely) hold and to succesfully train a Naive Bayes classifier.

I am inclined to disregard the independence assumption as it does not (neccesarily) stem from domain-knowledge, but is just a consequence of the simplifying assumptions inherent to Naive Bayes. Am i right in doing so?


texts: Combining Runtime Complexity Expressions with respect to Dijkstra

texts:
If I have an algorithm that fills out an $|V| \times |V|$ table with for loops and an $O(1)$ sub-problem after running Dijkstra twice (outside the loop), I think I get the following runtime complexity statement:

$$
O(\text{my algorithm}) = O(|V|\mathop{log}|V| + |E|\mathop{log}|V|) + O(|V|^2)
$$

Assuming Dijkstra's is implemented with the binary heap.

My problem is that I realized that, worst case, $|E| = |V|^2$, and the statement rewrites as:

$$
O(|V|^2 \mathop{log}|V|) + O(|V|^2) = O(|V|^2\mathop{log}|V|)
$$

But, the rest of the time, the algorithm is $O(|V|^2)$, especially if $|E| < |V|$.

What is the correct runtime in this situation? And what is the reasoning behind the correct runtime statement?  Because it seems like, to me, just listing out Dijkstra's runtime would be incorrect, since it is only true when the graph is dense... (can I add them together, like: $O(|V|^2 + |E|\mathop{log}|V|)$?)


texts: generalizing ball-bin problem to k-universal family

texts:
I am trying to solve a question in the book on Probability and Computing by Michael Mitzenmacher, Eli Upfal. The question asks to generalize ball-bin problem for 2-universal hashing to $k$-universal hashing.

In the standard bin-ball problem setup there are $n$ bins and $n$ balls. These $n$ balls are randomly thrown (independently) in $n$ boxes and we try to find maximum occupancy in any bin. This can be done by considering a hash function $h: [n] \to [n]$. We say that ball $i$ goes in bin $h(i)$. In this case hash function comes from a 2-universal family. It is shown that for 2-universal hash family, max occupancy is $l_{\max}=1+2\sqrt n$ with probability greater than $\frac{1}{2}$. It follows with usual application of Markov's inequality. Now we try to generalize this to hash $h$ coming from a $k$-universal family and find $l_{\max}$ so that max occupancy is less than that with probability $\frac{1}{2}$.

I tried to do following: First set up indicator variable as in previous case for 2-universal problem

$X_{ij}=1$ if ball i goes in bin $j$. Now load for bin $i$ is $X=\sum_{j=1}^{n}X_{ij}$.

Since hash is now $k$-universal we try to go for Markov on $k^{\text{th}}$ moment instead of Markov (which comes from 1-st moment) to get probability bound of $\frac{1}{2n}$. In the end we apply union bound. But I am unable to simplify expression for $k$-th moment in this context to get an answer.

Definition of $k$-universal hash function

$\mathrm{Pr}(h({i_{1}})=h({i_{2}})=\cdots=h({i_{k}}))= \frac{1}{n^{k-1}}$ for any $k$ distinct elements $i_1,\ldots,i_k$.


texts: Does 'subexponential algorithm' refer to input or number of bits used to represent input?

texts:
When an algorithm is said to be subexponential - does this refer to the input N or the number of bits used to represent N?  Consider the following: trial division for integer factorization (i.e. try all numbers less than $\sqrt N$) is subexponential in terms of N.

Note: here I'm using the definition of 'subexponential' to be $2^{O(n^\epsilon)}$ for some $\epsilon < 1$.

That is it takes $2^{\log_2 \sqrt N}$ steps to factor N.  This is obviously subexponential in terms of N.  However, in terms of the number of bits B needed to represent N this is $2^{\frac B 2}$ which is not subexponential in terms of B.

So would trial division be considered subexponential or not?  Or would it be considered both depending on whether you're referring to N or B?


texts: Number of bits needed to represent an integer with a specifed base

texts: How many bits are required to represent an integer $ x $ with base $b$?


texts: Isomorfism between inductive and coinductive types (through double negation)

texts:
The paper "CPS Translating Inductive and Coinductive Types" mentions that there is an isomorphism between inductive (mu) and coinductive (nu) types, which they use for their translation. It states that:

$$\neg\mu Z.A(\neg Z)\ \cong\ \nu Z.\neg A(Z)$$

...but it gives no more details about it. Is this isomorphism correct? Is it constructive? Where could I find more information about it?

I've spent several hours trying to prove (any side of) it on Coq, using the standard impredicative encodings for those (e.g., see here), but failed.


texts:
In "Typing Haskell in Haskell", by Mark P. Jones, is provided a sort of haskell-like specification for typing Haskell. As stated in this paper, binding groups is a area "neglected in most theoretical treatments of type inference". Jones provided inference and checking algorithms for this syntactic construct, but it's typing rule is not referenced.

As far I know, binding groups is quite differente from usual let bindings.
You can have mutual recursion, for example. Also, I don't know if is possible to simulate binding groups only using let expressions.

There is a typing rule for typing binding groups anywhere in the literature?
If there is, then maybe the rest of this question is pointless.

This paper also doesn't give us a (in)formal grammar for the syntax, because it's goal is type inference/checking from the data stucture itself. I don't think this is strictly necessary, but a syntactic definition of binding groups may help defining a typing rule. So, I decided to give a sugestion of what this informal grammar may look like. Brackets means finite sequence and curly bracket means no-empty finite sequence.

So, what I'm asking here is a rule for typing binding groups.

EDIT:

It seems that my question is not clear enough. I apologize for that. I'll try to make it more clear...

By typing rule (or type rule) I mean: en.wikipedia.org/wiki/Type_rule and by type checking algorithm I mean something easy to translate to code. I think the difference is more fundamental than just representation style. A rule is closer to a relation and an algorithm is closer to a function. What is missing is a rule, like in the wikipedia page, that could be used for certification of the algorithm.

Certification is the motivation behind my question. I want to certify the algorithms described in this paper.


texts:
A Markov chain with transition matrix $P$ is termed regular if for some $n$, all entries of $P^n$ are positive.
Is there a known notion of degree of regularity quantified in terms of how soon all entries are positive? That is, a Markov chain with transition matrix $P$ would be considered more regular than a Markov chain with transition matrix $Q$ if $P^n$ has positive entries but $Q^m$ only has positive entries for $m>n$.


texts:
Given a finite DAG $G = (V, E)$ with $|E| \in \mathcal{O}(|V|)$, I want to compute a total ordering $<$ over $V$ that is compatible to reachability: If there is a transition $(u, v) \in E$, then $u < v$.

The only way I could think of was to use Floyd-Warshall to compute a reachability matrix and then somehow extend that to be total. This would require cubic time, which is too slow for my needs. I require a quadratic time algorithm at most. In a publication I read that this is actually possible in linear time but no procedure or further explanation was provided.


texts:
I have a problem that asks me to consider the string abbbaacc. I'm supposed to figure out which of the following lexical specification produces the tokenization ab/bb/a/acc.

The options are:

A.
    a(b+c)*
    b+

B.
    ab
    b+
    ac*

C.
    c*
    b+
    ab
    ac*

D.
    b+
    ab*
    ac*

I just learned about REGEX, and I'm not sure about this, but to solve this problem would I just be trying see which options can make ab/bb/a/acc?

If that's correct, then would the answer be all four of them?

Since all four of them can match to ab/bb/a/acc:

A.
     a(b+c)* -> a, ab, acc
     b+ -> bb
B.
     ab -> ab
     b+ -> bb
     ac* -> a, acc
C.
     c* ->
     b+ -> bb
     ab -> ab
     ac* -> a, acc
D.
     b+ -> bb
     ab* -> a, ab
     ac* -> a, acc

I'm not sure if I'm doing this correctly.


texts: Asymptotics of a recurrence defined with two variables

texts:
What is the asymptotic behaviour, in Θ notation, of the smallest function that for any $n_1$ and $n_2$ satisfies the following:

$$t(n_1+n_2)≥t(n_1)+t(n_2)+c·\log_2(1+n_2)$$
where $n_1≥n_2≥1$ and $t(1)=1$

I tried to see what happens if $n_1 = n_2$:

$$t(2n)≥t(n)+t(n)+c·\log_2(1+n)$$
$$t(n)≥2t(n/2)+c·\log_2(1+n/2)$$

Also if $n_2=1$:

$$t(n+1)≥t(n)+t(1)+c·\log_2(2)$$
$$t(n)≥t(n-1)+1+c$$

But I am not sure where to go next, or if this is a correct approach.


texts: Determining asymptotic running time by profiling

texts:
The purpose of performance proﬁling is to measure program performance. One part of your PA1 assignment asked to measure performance of your d-smooth algorithm to verify if the running time of the program corresponds to the desired $O(n \log n)$. Assume that you have performed an experimental analysis of an algorithm, and proﬁling returned the following times: for instances of sizes $2^{10}, 2^{11}, 2^{12}, 2^{13}, 2^{14}$ the corresponding times are approximately 300, 500, 1100, 2900, 8300 milliseconds. There is an extra overhead resulting from clocking program performance and functions calls, and this overhead has to be considered in analyzing data. That is, the measured time consists of two components: the time for executing the operations, plus the overhead from proﬁling. The estimated overhead due to proﬁling is about 200 milliseconds independently of the input size. (that is, 200 is always an additive “constant”).
  Based on these experimental results, what is the running time for executing operations in this algorithm? ($c$ is a constant) In particular, is your implementation running in $O(n \log n)$?

  $c \log n$
  $c n$
  $c n \log n$
  $c n\sqrt{n}$ <----- Correct answer
  $c n^2$

(editor's note: I changed 81200 to 8300; the setters added 200 to 81000 instead of to 8100)

Why is $c n\sqrt n$ the correct answer?


texts: Minimum cost perfect matching (Using General graph

texts:
This is a continuation of the problem described in this topic: Optimized algorithm to match entities together based on heuristics. I've come a little closer as to what might be the best solution.

I've got a general graph of nodes that contains edges which relate nodes to each other. These edges have a cost, which is calculated using a euclidean distance.

Now I wish to find the maximum amount of matches between these nodes (Where every node can only be connected to one other node), and from there I want to find the "cheapest" result in reference to the cost of the edges.

Currently I've been trying to bruteforce this problem, where I would "look ahead" to minimize the amount of time spend, but it's come to a point where my datasets are so big, that I'd have to split them into smaller groups, as it simply takes too long to calculate the best result.

I've been looking into Edmonds blossom matching algorithm as it seems to fit my needs. (If adjusted to use edge costs'). But I'm having a hard time wrapping my head around the full scale of it.

I've been trying to find some "easy-to-read" examples and pseudocode of it, but it seems very hard to find one that specifically searches for the following criteras:

Most matches
Lowest cost
General graph (allow uneven number of nodes)

Does anyone know where I can find an example of some pseudocode that would fit the requirements above? Or maybe some working sourcecode in either C# or Java?


texts:
I have a problem where given an infinite binary sequence S ∈ {0, 1}∞ to be "prefix-repetitive" if there are infinitely many strings w ∈ {0, 1}*
such that ww is a prefix of S.

I need to prove that if the bits of a sequence S ∈ {0, 1}∞ are chosen by independent tosses of a fair coin, then
Prob[S is prefix-repetitive] = 0

My first instinct to tackling this problem was that the probability was 0, because of Cantor's diagonal argument, because we can construct an sequence s0 that is not in the set S. This would mean that S is countably infinite and the set of "all" possible infinite binary sequences is uncountable.

Any help or suggestions to see if I'm on the right track to proving this problem would be great!


texts:
I've watched multiple videos and read articles about recursion but I'm still confused. I've got this problem here but I'm unsure how to answer it:

  The following function calculates $x^n$ recursively. How many multiplications does the function make to calculate exp_rec(2, 64)?

def exp_rec(x, n):
    if n==1:
       return x
    else:
        p = exp_rec(n, x-1)
        return x*p

Could someone help explain?


texts: Time complexity of Vertex Cover vs Clique for fixed k

texts:
I have 2 ways of solving Independent Set problem of fixed size $k$ for graph $G = (V, E)$:
- Vertex Cover algorithm running in $O^*(1.47^{V - k})$ (optimized recursive algorithm)
- Clique algorithm running in $O({V\choose k})$ (simple enumerate subsets of $V$ and check algorithm)

How can I determine which one has a lower time complexity? I'm not very familiar with algorithms for NP-complete problems and $O^*$ notation. Would plotting those functions suffice? I think that VC algorithm can have any polynomial $n^{O(1)}$ as a multiplication because of the $O^*$ notation and this could affect the running times, but I'm not sure.


texts:
1) In Booth's bit-pair recording technique how to multiply a multiplicand with 2?

2) In booth's algorithm for multiplication/Booth's bit-pair recording of multipliers, the sign bit extension of the multiplicand i.e. we must extend the sign-bit value of the multiplicand to the left as far as the product will extend. Now my question is what should be the value of extended Sign Bit?

I think following are the possible values-

Multiplier  Bit, Extended sign bit value

i)      0,                                               0

ii)       +1,                                               0

iii)      -1,                                               1

iv)       -2,                                               1

v)         2,                                            I don't know

Also, why is the sign bit extended? Will we get the correct answer if we  don't extend sign bit?


texts: Do we know of any necessary condition for a Boolean function or say a depth $2$ LTF circuit to have a low (~poly(dim)) sign-rank?


texts:
One common observation in type systems is that having subtyping makes type inference hard [1]. Consequently, for records, many modern functional languages shun subtyping (OO style) in favor of row polymorphism. Some examples include:

Ur/Web - duplicate labels are disallowed, the programmer uses first class disjointedness proofs to combine records.
Koka - duplicate labels are allowed and are used to encode effects [2].
Purescript - duplicate labels are allowed and are used to encode effects [3].

ML-style module systems may be thought of as extending records by allowing type definitions and abstraction as well, along with all the complications those entail, such as recursive definition, preservation/loss of type equalities etc.

SML and OCaml's (and probably many other MLs') module systems allow subtyping. Also, OCaml doesn't offer much in terms of type inference for module signatures (I'm assuming SML is similar here).

Q: Is there an equivalent of row polymorphism at the module level?  (I mean something documented in the literature or used in some existing language). Something that would make the following type-check:

module type S1 R = { type t; val f1 : t -> int; | R }
module type S2 R = { type t; val f2 : t -> int; | R }
functor F (M : S1 R) : S2 R = { type t = M.t; let f2 x = f1 x * 2 | R }

module M : S1 { type u; } = {
  type t = char;
  let f1 = atoi;
  type u = Traveller;
}

(* Arrived! *)
type traveller = (F M).u

It seems plausible that something like Ur/Web's system would work as you'd want to enforce uniqueness of type definitions and not have the order of definition matter.

If such a system does exist, please provide citations :). If not, please try to provide an explanation at the level of an introductory type theory book (e.g. Pierce's Types and Programming Languages) of why this wouldn't work [4].

Note: While this question specifically asks about ML-style modules, answers related to mixin modules are also welcome (although I'm only very vaguely familiar with them).

[1] Yes, I know about the Algebraic Subtyping paper which shows an alternate approach, but that is relatively recent work.

[2] Leijen, Daan. "Koka: Programming with row polymorphic effect types." arXiv preprint arXiv:1406.2061 (2014).

[3] https://github.com/purescript/documentation/blob/master/language/Types.md#rows

[4] I had a quick look at the 8th chapter in Pierce's Advanced Topics in Types and Programming Languages which goes over ML modules in quite some detail. It seems to take subtyping as a given, for understandable reasons.


texts:
I have encountered a variant of the knapsack problem with shrinking items.

Effectively, it is a 0-1 knapsack problem where the initial weight of each item is $W(n)+V(n)$ and their value is $V(N)$, but immediately after being put into the container the item shrinks by $W(n)$. This means that for every item IN the knapsack, weight and value are the same. (It is therefore also possible to look at this as a value-irrelevant "best fill only" 0-1 knapsack.)

So, in this case, one also needs to determine the proper order of items to insert and whether a specific item is legal in the combination before being put in the container.

I have already determined that order of insertion, given a valid collection, should be based on $W(n)+V(n)$ descending—but thus far I am failing to create a set of valid collections in anything under $O(2^n)$.

Dynamic programming solutions are failing me both because of the apparent interdependence of elements which makes memoization seemingly impossible.

I realize I have not given much here, but I could really use some help. How does one go about approaching this variant?

If curious, the actual application is that we have a large number of different electrical appliances that all cause a known power surge when turned on and afterwards draw a set amount of power. We never want to trip a breaker, so the surge needs to be taken into account when figuring out how many at most we can turn on.


texts: Approximation scheme for Multiple Choice Knapsack

texts: The paper _Fast Approximation Algorithms for Knapsack Problems (E. Lawler, 1979) gives an FPTAS (fully polynomial time approximation scheme) for the multiple choice knapsack problem (MKP). But MKP is strongly NP-hard, so it cannot have an FPTAS unless P=NP. Is the result of this paper wrong?


texts: Has the problem of finding the most profitable transactions given a set of discrete time series been well-studied?

texts:
Overview and Problem Description
Suppose I have a set of N discrete time-series (represented as a map from time-interval-index to value/utility), and I would like to identify a sequence of actions in a particular time interval that would yield the highest profit at the end of the interval (assuming there is a transaction cost T associated with selling your holdings in a given time series). Problem Inputs include (i) transaction cost (volume-independent fixed cost) , (ii) price tables of alternatives (indexed by time step), and the (iii) time interval in question. Problem Output is a sequence of tuples (timestep, decision type) that maximizes returns at the end of the interval. Valid decisions include buying and selling ones funds from one alternative to another at discrete time steps.
Trivial Example
You have USD 1 in year 1 [Problem Input]. Given Stocks A and B prices in years 1, 2, and 3, determine the sequence of actions that will maximize your profit at the end of the interval [1, 3]. The transaction cost, independently of volume, is USD1 [Problem Input]. You can sell and buy into any time series by paying the transaction cost for the trade at any discrete time step.
Stock A [Problem Input]:
Year 1: USD 1
Year 2: USD 1.1
Year 3: USD 1.2
Stock B [Problem Input]:
Year 1: USD 1
Year 2: USD 1.2
Year 3: USD 0.9
Answer [Problem Output]: Buy Stock A in year 1.
Buying Stock B for the first year would result in a higher return from the stock itself. However, given the USD 1 transaction cost, it's better to hold Stock A.
Question
I have a feeling this problem is well-studied. I can see how it would have a lot of applications, even though one usually does not have perfect information.
If I'm correct about my hunch, what is this problem called?
Of course you could just formulate this as an integer program, but I'm looking for a solution approach that's less 'naive' (if that even exists).


texts: Can solutions to the graph coloring problem be used in the prison system to keep known enemies apart with the goal of reducing violence?


texts: All paths of length n from a single graph vertex in a directed cyclic graph

texts:
Thanks in advance...looking for recommendations on an algorithm to find all paths of length n starting from a single node in a directed, cyclic graph.

I am not concerned with at which node the path completes. i.e. not looking to travel from i to j in a path of a certain length. I would like to start from i and end ultimately with an enumeration of all unique paths emanating from i of length n. These unique paths may or may not contain cycles.


texts:
I'm learning by my self about OS theory and I have some troubles to understand what is a process address space. So far, I came across two definitions of what a process address space is:
1 - The set of virtual addresses available to a process. Hence the address space, would be the numbers from 0x0 to 0x7FFFFFFF.
2 - The virtual memory addressable by a process. I picture it as a set of cells with addresses from 0x0 to 0x7FFFFFFF.

I would like to know which one is correct?
This is important for me because I read sentences like "the address space is organized into pages of 4096 bytes" which makes me lean towards the second definition.

Thank you.


texts: Data structure for sparse matrices for an online problem

texts:
I need to compute a large linear optimization problem very often after recieving updates to my optimization problem.

That is I have a linear problem to find an x such that

$x_1 * c_1 + ... + x_n * c_n$ is as small as possible

under the conditions that $Ax \# b$ (where $\#$ can be $<=$, $>=$ or $=$ on each row).

At some (small) time interval the $a_{ij}$, $c_i$ and $b_i$ can get updates and I need to recompute. The updates only touch very few of the entries and most of the time the changes are only by small amounts.

Some of the $x_i$ are integer variables, some are binary variables and some are real variables.

Current idea:

find a sparse matrix data structure which allows for efficient updates
implement a branch-and-bound algorithm which works on that data structure

Question: which combination of sparse matrix representation and linear optimization algorithm is the current state of the art for such a problem?

Sub-question: is there a way to use the result from the previous run if I know only a few entries change?


texts: Why are MM-1QFA strictly more powerful than MO-1QFA?

texts:
While dealing with quantum finite automata (QFA), I repeatedly come across the statement that measure-many QFA (MM-1QFA, KW97) are strictly more powerful than measure-once QFA (MO-1QFA, MC97); both models are sufficiently described in this Wikipedia article.

So far, I found a proof in L19 (p.5, prop.1) which shows that, for any MO-1QFA and any input string w, there is an MM-1QFA accepting w with the same probability (only bounded error considered here). Therefore, MO-1QFA = MM-1QFA.
However, I have not been able to find a proof showing that MM-1QFA > MO-1QFA indeed. There are informal arguments by Brodsky and Pippenger BP18 (p.9, start of sec.4), just saying that this is because MM-1QFA are allowed to terminate before reading the entire input string (due to their measurements after every transition). Furthermore, Ambainis and Freivalds AF98 (end of p.3) say that any finite language can be recognized by MM-1QFA, but no finite non-empty language can be recognized by MO-1QFA.

Though these claims seem reasonable to me at first, I have failed to construct an example (let alone an idea for a general proof) that would make them clear to me. One issue is that I do not see how a MM-1QFA would know "when to stop".

Based on all this, I would be glad if someone could help me to see why MM-1QFA are strictly more powerful than MO-1QFA.


texts: Betweenness centrality and least average shortest path

texts:
TL;DR: How do I justify mathematically that vertices with the highest betweenness centrality do not necessarily have the smallest mean shortest path?

I am currently studying the London Underground as a hobby. Recently, I have been calculating some graph metrics for different vertices (ie. Tube stations) in the London Underground network.
From my calculations, the top 5 stations for betweenness centrality are

Baker Street               0.344084
King's Cross St.Pancras    0.303868
Liverpool Street           0.267392
Green Park                 0.263264
Mile End                   0.229449

After that, I calculated the mean shortest path from each station to every other station and the top 5 stations (smallest mean shortest paths) were

Green Park       8.901887
Oxford Circus    9.007547
Bond Street      9.090566
Baker Street     9.211321
Westminster      9.339623

I was expecting the station with the highest betweenness centrality to have the smallest mean shortest path and the data proved me wrong.  I am looking for a more mathematically rigorous justification for why greatest betweenness does not imply least average shortest path.
All ideas and hints are appreciated.


texts:
I was recently in an interview and was asked what would be the smallest memory foot print and fastest system to check if a given phone number is in your data store given that all phone numbers will only be 7 digits.

I was told the answer is a byte but, I'm still not 100% sure how this would work and have not been able to find any information on it as of yet. If anyone knows the name of the structure/algorithm or would be willing to explain it I would be very appreciative.

Example data set:
6041234567
6041234568
6041234569
6041234570
6041234571

Output if checking for 6041234569:
True

Output if checking for 6041234580:
False

Edit: Please ask questions so I can try and make my question more clear.
Edit2: I only need to know if the phone number exists. I don't need to get it out.


texts: Does indirect diagonalization a relativize technique?

texts:
My main question is can with R.kanon , Fortnow ,... technique that shows lower bounds for SAT seperate P and NP ?

Baker-Gill-Solovay showed that $P?=NP$ could not be solved with relativization. Does indirect diagonalization a relativized proof?

Suppose with indirect diagonalization  we show that $NP\not\subset A$ (A is an arbitrary class). how $A$ class can be big with indirect diagonalization technique?(I know it is possible that $TISP(n^{1.8},polylog n)=P$ and the bigger class for me is P or $TISP(n^{O(1)},polylog n)=P$ ). we know that $A$ is at least $TISP(n^{1.8},polylog(n))$(class of languages decides with $O(n^{1.8})$ time and $O(polylog(n))$ space simultaneous).

According to Baker-Gill-Solovay proof I think this approach can not seperate P and NP with indirect diagonalization according this pdf. that mentioned "we will show that such techniques alone cannot prove NP=P"

In special case I want to know that if someone shows $NP\not \subset TISP(n^{O(1)},poly(\log(n)))$ with indirect diagonalization ?


texts: General start rule question for a context free grammar

texts:
Suppose I have a context free grammar described:

  $S \rightarrow 0SS1$
     $S \rightarrow 1$
     $S \rightarrow \epsilon$

Because the first rule is considered the start rule does that mean that this grammar could never generate a string that starts with 1 or can you apply the second $S$ rule first to generate the string?


texts:
I am currently studying for my exam and I am having trouble to solve this question:

Right or wrong: If $A$ is context-free then $A^*$ is regular.

I think it's wrong because if $A$ is context-free it means that $A$ can be a non-regular language. And the non-regular languages are not closed under the Kleene star operation (at least I think so). I am not sure how write this in a more formal way.
Maybe like this?
Let $A=\{a^nb^n \mid n \in \mathbb{N}\}$. Then we know that $A$ is non-regular and context-free. However, I'm not sure what $A^*$ is.


texts: Term of System F whose type-erasure is $2(2)$

texts: If $2$ is the Church numeral $\lambda fx. f(f(x))$, then is there a closed term $t$ of System F of type $\forall \alpha ((\alpha \to \alpha) \to (\alpha \to \alpha))$ such that the type-erasure of $t$ is the untyped term $2(2)$?


texts: Computing automaton for $L(A) / L(B)$ gives ones for $A,B$

texts:
I'm trying to figure out whether infinite language change the answer.

Show that the following language is decidable:
$$L=\{\langle A,B \rangle : \text{$A,B$ are DFAs, $L(B)$ is finite, and $L(A)/ L(B)=L(0^*1^*)$}\}.$$

(I am talking about right division.)
We know how to check whether the language of a DFA is finite, and given two DFAs, we know how to check whether their languages are equal. The algorithms I know to the above problems uses the DFA's, so it is necessary having the DFA's in order to decide those problems.
I'm trying to figure out whether $|L(B)|=\infty$ changes the answer. To the best of my understanding, because $|L(B)|<\infty$, we can explicitly construct a DFA that accepts $L(A)/ L(B)$, whereas if $L (B)=\infty$ all we know is about the existence of $DFA$ that accepts $L(A)/ L(B)$.
However, even if $L(B)$ is an infinite language, since there is a finite number of DFAs, one of which accepts $L(A) / L(B)$, I can certainly know that there is a Turing machine that decides the language $L$.
Right?


texts:
As I understand, the concept 'computation' started dependent on hardware (like looms for instance).

The Hardware defines (physical cascades) what happens between input and output.
I think I saw in a CS class, a mention about universal calculation where software is not limited by hardware?

It's hard to find a succint answer.
What makes a universal calculator, universal?

(I'm not a CS major, so forgive my unprofessional terms and wordings)
Thank you.


texts:
Suppose I have $N$ bins and $M$ items as depicted in the figure below (3 bins and 3 items):

Suppose that every bin has unit capacity and the weights of the items depend on the bins used. I want to maximize the number of items in the bins subject to:

One bin contains at most one item.
If item $i$ is on bin $j$ then $g_{ij}\geq1$ must hold now if all other bins are empty.
If item $i$ is on bin $j$ (so $g_{ij}\geq1$ must hold now) and item $i^\prime$ is on bin $j^\prime$, then $g_{ij}\geq g_{ij^\prime}$ and $g_{i^\prime j^\prime}\geq g_{i^\prime j}$ must both hold now.
If item $i$ is on bin $j$ (so $g_{ij}\geq1$ must hold now) and item $i^\prime$ is on bin $j^\prime$ (so $g_{ij}\geq g_{ij^\prime}$ and $g_{i^\prime j^\prime}\geq g_{i^\prime j}$ must both hold now) and item $i^{\prime\prime}$ is on bin $j^{\prime\prime}$, then $g_{ij}\geq g_{ij^\prime}+g_{ij^{\prime\prime}}$ and $g_{i^\prime j^\prime}\geq g_{i^\prime j}+g_{i^\prime j^{\prime\prime}}$ and $g_{i^{\prime\prime} j^{\prime\prime}}\geq g_{i^{\prime\prime} j}+g_{i^{\prime\prime} j^{\prime}}$ must all hold now.
And so on and so forth.
In general I will have the following constraint: $g_{ij}x_{ij}\geq\sum\limits_{i^\prime=1,\;i^\prime \neq i}^{M}\sum\limits_{j^\prime=1,\;j^\prime \neq j}^{N}g_{ij^\prime}x_{i^\prime j^\prime}$, where $x_{ij}$ equals $1$ if item $i$ is in bin $j$ and equals $0$ otherwise.

Finally, I have the following problem:

Maximize $\sum\limits_{i=1}^{M}\sum\limits_{j=1}^{N}x_{ij}$

subject to

$\frac{g_{ij}x_{ij}}{\sum\limits_{i^\prime=1,\;i^\prime \neq i}^{M}\sum\limits_{j^\prime=1,\;j^\prime \neq j}^{N}g_{ij^\prime}x_{i^\prime j^\prime}}\geq x_{ij},\; \forall i, j,$ (C1)
$\sum\limits_{j=1}^{N}x_{ij}\leq1,\; \forall i,$ (C2)
$\sum\limits_{i=1}^{M}x_{ij}\leq1,\; \forall j,$ (C3)

and $x_{ij}\in\{0, 1\},\; \forall i, j,$ (C4)

The input of the problem is $M$, $N$, and $g_{ij},\;\forall i,j$. The right hand side of constraint (C1) is to say that when item $i$ is not in bin $j$ (i.e., $x_{ij}=0$) then (C1) is not violated. (C2) and (C3) say that one item goes to one bin and one bin contains one item, respectively. Finally, (C4) is the variable of the problem which is a binary variable.

My question is: Can I say that this problem is a bin packing problem and it is therefore NP-hard? If not, Can you suggest a reduction idea from an NP-complete problem?

Thank you for your help.


texts: How to find the language of a CFG from Production rules

texts:
I'm having problems in finding language of the CFG from given production rules. For example if the production rules are
\begin{align}
&S \to AS \mid \epsilon \\
&A \to aa \mid ab \mid ba \mid bb
\end{align}
How can I find the language it describes?


texts: Detecting cycles in directed graphs where basic operations have high complexity

texts:
Given a directed graph $G=(V,E)$, we know that there are efficient algorithms (i.e., linear in the number of nodes and edges) for detecting cycles in it. But this uses the fact that a basic task such as determining whether there is a vertex from $v_1$ to $v_2$ is easy.

Suppose, however, that the size of $G$ (i.e., the number of nodes) is exponential, and that, given $v_1,v_2\in G$, the complexity of determining whether there is an edge from $v_1$ to $v_2$ is $\mathsf{PSPACE}$-complete.

My question is: given only this amount of information, is it somehow obvious/straightforward what the complexity of finding a cycle in $G$ is (e.g., whether it is $\mathsf{EXPTIME}$-hard, or something like that)?

As a sidenote, I haven't said where these graphs come from. They're some combinatorial objects generated from some other stuff, and I'm curious whether the complexity issue needs a bona-fide reduction using the particulars of the situation, or if there's some quick general argument that applies here, and which I'm missing.


texts: How can simulated annealing be related to the vehicle routing problem?

texts:
I have been searching through internet how could simulated annealing to solve the vehicle routing problem, but didn't find anything that made it clear to me. Most of what I found are research papers intended to solve some specific variation of the routing problem.

So I would appreciate if someone can make some kind of explanation of possible ways two things can be related and give some links that to so.


texts: Randomized Quick Selects' time complexity dependence on k - the index to be selected

texts:
I was analyzing Randomized Quick Selects' time complexity, as a function of n - the size of the input, and k - the index of the element that needs to be selected.
The time complexity dependence on n was linear as was expected, but the dependence on k was of an inverted parabola - i.e the time complexity was highest when trying to select the median and lowest when trying to select the first or last element of the array.

Is there an explanation for that?


texts: Solve Integer Factoring in randomized polynomial time with an oracle for square root modulo $n$

texts:
I'm trying to solve exercise 6.5 on page 309 from Richard Crandall's "Prime numbers - A computational perspective". It basically asks for an algorithm to factor integers in randomized polynomial time given an oracle for taking square roots modulo $n$.

I think, the basic idea is the following: Given a composite number $n$, to take a random element $r$ in $\left.\mathbb{Z}\middle/n\mathbb{Z}\right.$ and square it. If $r$ was a square, $r^2$ can have up to $4$ different square roots and the basic idea of the algorithm is that the oracle has some chance not to choose $\pm r$, but one of the other two roots. It will turn out that we then can determine a factor of $n$ using Euclidean's algorithm.

I formalized this to

Input: $n=pq\in\mathbb{Z}$ with primes $p$ and $q$.

Output: $p$ or $q$

Take a random number $r$ between $1$ and $n-1$
If $r\mid n$ then return $r$ (we were lucky)
$s:= r^2\pmod{n}$
$t:=\sqrt{s}\pmod{n}$ (using the oracle)
If $t\equiv \pm r\pmod{n}$ then goto step 1.
Return $\gcd(t-r,n)$

One can show that $t \not\equiv \pm r\pmod{n}$ implies that $\gcd(t-r,n)\neq 1,n$ and therefore get that the return value of the algorithm is a non-trivial factor of $n$.

Inspired by my main question "How do I prove that the running time is polynomial in the bit-size of the input?" I have some follow up questions:

Do I have to show that a lot of numbers between $1$ and $n-1$ are squares? There must be a well-known theorem or easy fact that shows this (well... not well-known to me ;-).
Are there any more details I have consider?
Has every square of a square exactly $4$ square roots modulo $n$?


texts: How should I describe the relationships between type expressions?

texts:
Lets say I have two type expressions: Maybe a (X) and Maybe Integer (Y), where Maybe is a type constructor, Integer is a Type  and a is a type variable.

What language should I use to describe the relationship between these expressions, and type expressions in general? I've been using the language of sets: X describes a subset of Y, X and Y intersect, and so on. Is this generally accepted, or is there a different, widely accepted language for describing the relationships between type expressions?

In the example provided, I would like to express th at expression X describes many possible types, and that includes all of the types described by Y.


texts: Proving a certain hypothesis class on a given distribution is not learnable

texts:
I had this question in Learning theory, but it's really just a question in probability theory to be honest, so I'm gonna try to rephrase it in a way that really emphasizes what I was trying to do to solve it:

Let $\mathcal X_N=\{0,1\}^N$, $\mathcal Y=\{0,1\}$ and define a uniform distribution, $\mathcal D_N$, on $\mathcal X_N \times \mathcal Y$. Prove that for any $m, \epsilon\in(0,\frac{1}{2}), \delta \in(0,1)$ there exists a number $N$ such that $\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: L_\mathcal D(i) > \epsilon \,\wedge \forall \, 1\leq j \leq m, \,x_j(i)=y_j)>\delta$
Original phrasing:
Let $\mathcal X_N=\{0,1\}^N$, $\mathcal Y=\{0,1\}$ and define a uniform distribution, $\mathcal D_N$, on $\mathcal X_N \times \mathcal Y$. Define the hypothesis class $\mathcal H_N = \{h_i: \mathcal X_N \to \mathcal Y \mid 1 \leq i \leq N \}$, where $h_i(x) = x(i)$.
Prove that for any $m, \epsilon\in(0,\frac{1}{2}), \delta \in(0,1)$ there exists a number $N$ such that $\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: L_\mathcal D(i) > \epsilon \,\wedge L_S(h)=0)>\delta$

So a few things:
$S$ is obtained by randomly and independently drawing $(x,y)$ pairs from $\mathcal D_N$,
$L_D(i) = \mathbb P_{(x,y)\sim \mathcal D} (x(i)\neq y)$,
x(i) - is the i'th coordinate of the $N$ dimensional vector x.
What I tried to do was:
First of all, fix an $i\in \{1,...,N\}$ and consider $\mathbb P_{(x,y)\sim \mathcal D} (x(i)\neq y) = 2\frac{2^{N-1}}{2^{N+1}} = \frac{1}{2} > \epsilon $ for any $\epsilon \in (0,\frac{1}{2})$ so the first requirement is rather redundant.
Second, independently drawing a sequence $S$ of $m$ pairs (with repetition) such that every pair has $x(i)=y$ is with probability $\mathbb P_{S\sim \mathcal D^m} (\forall \, 1\leq j \leq m : x_j(i)=y_j) = \prod_{j=1}^m \mathbb P_{(x,y)\sim \mathcal D} (x_j(i)=y_j) = \frac{1}{2^m}$.
Now that's for a single fixed $i\in [N]$, trying to lower bound the probability of an existence of such an $i$ could either be done by just ignoring the rest and saying $\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: \forall \, 1\leq j \leq m, \,x_j(i)=y_j)\geq \frac{1}{2^m} > \delta$
But that is a very gross estimation so I calculated the probability exactly using inclusion-exclusion principle like so:
let $1 \leq i_1 < i_2 <... < i_k \leq N\,$ then $\mathbb P_{S\sim \mathcal D^m} (\bigwedge_{t=1}^k \{ \forall \, 1\leq j \leq m, \,x_j(i_t)=y_j\}) = (\prod_{t=1}^k \mathbb P_{S\sim \mathcal D^m} (x(i)=y))^m = \frac{1}{2^{km}}$
finally we get:
$\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: \forall \, 1\leq j \leq m, \,x_j(i)=y_j) =
 \sum_{i=1}^N (-1)^{i-1}{{N}\choose{i}}(\frac{1}{2^m})^i$
And now my goal is to lower bound this by $\delta$ and using some closed form of this expression.
My question is first, is my analysis even correct and second, how would you proceed?
Thanks in advance!


texts: If $L$ is a subset of $\{0\}^*$, then how can we show that $L^*$ is regular?

texts:
Say, $L \subseteq \{0\}^*$. Then how can we prove that $L^*$ is regular?

If $L$ is regular, then of course $L^*$ is also regular. If $L$ is finite, then it is regular and again $L^*$ is regular.
Also I have noticed that, for $L = \{0^p \mid p \text{ is a prime}\}$, $L$ is not regular, $L \subseteq \{0\}^*$ and $L^*$ is regular.

But how to show this for any subset $L$ of $\{0\}^*$ ?


texts: Why do we need to change the (weight decay) regularization parameter when changing the number of inputs that neural network is being trained with?

texts:
I am currently working my way through Michael Nielsen's ebook Neural Networks and Deep Learning and I am reading about overfitting and (L2) regularization. In this subsection, the process of L2 (a.k.a weight decay) regularization is introduced as being the process of adding the term
$$
\frac{\lambda}{2n} \sum w^2
$$
to the cost function so that it becomes
$$
C = C_0 + \frac{\lambda}{2n} \sum w^2
$$
where $C_0$ is the original cost function, $\lambda$ is the regularization parameter, $n$ is the number of items of training data being used, and the sum is over all of the weights in the network.

Later in this chapter, the process of choosing hyperparameters is discussed and the following is said:

  In the above example [when we were using a training set of size 10,000] I left $\lambda$ as $\lambda = 1000.0$, as we used earlier. But since we changed the number of training examples [to 1,000] we should really change $\lambda$ to keep the weight decay the same. That means changing $\lambda$ to $20.0$.

Why would changing the number of training examples mean that we should change the value of the regularization parameter $\lambda$?


texts: Set of vertex-disjoint cycles maximizing different colored vertices

texts:
Let $G=(V,E)$ be a directed graph whose vertices $v \in V$ have colors and its edges $e\in E$ have costs $cost(e)$.

I am looking to find a set of vertex-disjoint cycles that:

First maximizes the number of differently colored covered vertices.
In case of ties, break ties by secondly maximizing the number of chosen edges.
In case of any further ties, third minimizes the total cost of the chosen edges.

This is very similar to this problem, with additional constraint (#1). Without the first constraint (maximize the colors) this problem is easily solved by:

Splitting each vertex $v$ to $v^+$ and $v^-$.
Each vertex $v^+$ and $v^-$ provides a supply of $+1$ and $-1$, respectively.
Replacing an original edge $e': v \to w$ with $e: v^+ \to w^-$. Such each edge has cost $cost(e') = cost(e)$ and unit capacity.
Adding a "bind" edge $e'' : v^+ \to v^-$. Its cost is $c(e'') \gg 1$

Here is a representation:

And the problem has been reduced to a minimum-flow problem (MCF). A MCF algorithm will choose $A_1 \to B_1 \to A_2 \to B2 \to A_3 \to B_3 \to A_1$.

My question: is it possible to apply a similar modeling to satisfy the color constraint in polynomial time? If so, is it possible to reduce the problem to a MCF problem?

Here is how far I have managed to take it:

Here, bind-edges $e''$ go through a collective set of nodes, one per color, e.g., "A no+" and "A no-". These represent the corresponding vertices not chosen. Between "A no+" and "A no-" three edges are added with unit capacities and costs $ c(e_{red}) >> c(e_{orange}) >> 1$

I basically model that the cost of not choosing one or even two yellow items is insignificant to the cost of not choosing all three yellow items. Therefore, the goal is to choose $A_1 \to C \to B_3 \to A_1$.

Nevertheless, this did not quite work. Basically, if a flow goes through $A_1^+ \to A_{no}^+ \to A_{no}^-$, it's not guaranteed that it will return to $A_1^-$.

I have tried other approaches, including toying around with non-unit capacities, but I didn't find a solution. Can it be solved in polynomial time?


texts: Complexity of recursion T(n) = 2T(n-1) + C?

texts:
I am trying to calculate the Time Complexity of the Recursive Function, suppose this,

function T(int n){
 if(n == 1) return 1;
 return T(n-1) + T(n-1);
}

the time complexity equation is: T(n) = 2T(n-1) + C, taking C = 1 and T(1) = 1.
Now, since I am working on this, I am confused whether I am doing the right process using Back Substitution. This is how I approached the calculation.
I have followed the below question, but did not find it very satisfactory, so raising the question again.

Complexity of Recursion T(n) Function

This is how I approached the problem:

1. T(n) = 2T(n-1) + 1
2. T(n-1) = 2T(n-2) + 1 //since we have T(n-1) in Eq(1)
3. T(n-2) = 2T(n-3) + 1 //since we have T(n-2) in Eq(2)

Back Substitution to Solve for final complexity

1. T(n-1) = 2(2T(n-3) + 1) + 1
2. T(n) = 2(2(2T(n-3) + 1) + 1) + 1
        = 2(4T(n-3) + 1 + 2) + 1
        = 8T(n-3) + 1 + 6
        = 8T(n-3) + 7
        = 8T(n-3) // Ignoring 7, since it is a constant
        = 2^3T(n-3)
        = 2^kT(n-k)

Substituting the value of K, since base case is n = 1

1. n-k = 1
2. k = n-1

//Substituting the value of k in the above T(n) Equation
T(n) = 2^{n-1}T(n-n+1)
     = 2^{n-1}T(1)
     = 2^{n-1} * 1
     = 2^{n-1}

So from above I got 2n-1, is the above process correct, or needs improvement. I am starting off with time complexity, and this recursion is kind of tricky for me. Please help!


texts: How do we generate a depth-first forest from the Depth First Search?

texts:
I was trying to implement an algorithm which finds the strongly connected components (SCC's) of a directed graph. In order to find the SCC's, as the last step we need to be able to generate the Depth-First Search Forest as mentioned in CLRS:

STRONGLY-CONNECTED-COMPONENTS (G)

 1. Call DFS(G) to compute finishing times f[u] for all u.
 2. Compute G^T
 3. Call DFS(G^T), but in the main loop, consider vertices in order of decreasing f[u] (as computed in first DFS)
 4. Output the vertices in each tree of the depth-first forest formed in second DFS as a separate SCC.

However, I did not understand how to generate the DFS Forests from the Depth First Search. Please explain me how is it possible, and preferably use Cormen's DFS Psuedocode as I am a beginner and am quite familiar with CLRS.

Below is Cormen's DFS psuedocode:

DFS (V, E)

1.     for each vertex u in V[G]
2.        do color[u] ← WHITE
3.                π[u] ← NIL
4.     time ← 0
5.     for each vertex u in V[G]
6.        do if color[u] ← WHITE
7.                then DFS-Visit(u)              ▷ build a new DFS-tree from u

DFS-Visit(u)

1.     color[u] ← GRAY                         ▷ discover u
2.     time ← time + 1
3.     d[u] ← time
4.     for each vertex v adjacent to u     ▷ explore (u, v)
5.        do if color[v] ← WHITE
6.                then π[v] ← u
7.                        DFS-Visit(v)
8.     color[u] ← BLACK
9.     time ← time + 1
10.   f[u] ← time                                 ▷ we are done with u

PS: Rest assured, this is not homework.


texts:
I am citing the definition of the Hitting Set Problem from (Gardy & Johnson, 1979):

  INSTANCE: Collection $C$ of subsets of a set $S$, a positive integer $K$.

  QUESTION: Does $S$ contains a hitting set for $C$ of size $K$ or less, that is, a subset $S' \subseteq S$ with $|S'| \leq k$ and such that $S'$ contains at least one element from each subset in $C$?

The problem definitions from other sources (none of which elaborates on the size of $C$ in relation to $|S|$):

https://theory.stanford.edu/~virgi/cs267/lecture5.pdf

http://cs.indstate.edu/~arash/algo2lec8.pdf

http://www.et.byu.edu/~jka/521/slides/lecture22.pdf

http://www.cs.toronto.edu/~lalla/373s14/assignments/A3Sol.pdf

http://www.cse.iitd.ernet.in/~amitk/SemI-2015/tut12.pdf

Given a set $S$ with $|S| = n$, a collection $C$ of its subsets can have up to $2^n$ elements (where each element is a subset of $S$).

Given a certificate, $S' \subseteq S$, of the Hitting Set Problem, how could we possibly check if $S'$ contains at least one element from each subset in $C$ in polynomial time w.r.t $n$?


texts:
I'm having trouble understanding some language notation, primarily what rules I can take away from it. The language is as follows:

$\qquad L = \{a^n b^m b^p c^p b^{n-m} \mid n > 0, m < n, p > 2\}$

My goal is to create a context free grammar from this, but I can't get my ahead around the rules in place here. In plain English, it's clear that any string for this language must have a positive number of a's in it, but what is going on with the multiple b's? Do I take this as the string must be in some form like so:

$\qquad aaa-b-bbb-ccc-bb$  (n=3, m=1, p=3)

where the bunches of b's are just distinct sequences? Or is there something else I should be doing in order to satisfy this?


texts: Solving a graph problem by Gaussian elimination

texts:
I have been given a graph with n nodes. Now, I have to color every node of this graph by k colors, number from 0 to k-1. Now, there is a rule.

For a node $x$ with adjacent nodes $y_1 , y_2, y_3, y_4,... y_m$, $color(x)=(color(y_1)+color(y_2)+color(y_3)+...+color(y_m)) \pmod k $

where $color(a)$ indicates a color number from 0 to k-1. I have to find number of ways I can color the whole graph.

My approach to the problem was simple. I was constructing a $n*n$ matrix for n nodes in graph with equations like $col(x)-col(y_1)-col(y_2)-col(y_3)...-col(y_m)$. And trying to find number of all zero rows, which will provide us number of free variable. Is my approach correct?


texts: Logic formula for exactly n unique objects (no more, no less)

texts:
I have a question in Logic:

If I am asked to construct a formula, using the '=' predicate, that shows that there are exactly n objects, I need to show that there are no n+1 objects, right?

For example, to show that there are exactly 3 objects, I will show that there are no 4 objects.

Also, I need to show that there exist n objects.

My question is, do I need to show that there is no case where only n-1 objects exist?

For example, to show that there are exactly 3 objects, do I need to show that there is no case in which there are only 2 objects?

If so, is that the correct form to do so? :

1) Showing that there is no case of 4 elements:

$
{\lnot}{\exists}x{\exists}y{\exists}z{\exists}w(x{\neq}y{\land}x{\neq}z{\land}x{\neq}w{\land}y{\neq}z{\land}y{\neq}w{\land}z{\neq}w)
$

2) Showing that there are 3 elements:

$
{\exists}x{\exists}y{\exists}z(x{\neq}y{\land}x{\neq}z{\land}y{\neq}z)
$

3) Showing that there is no case of only 2 elements:

$
{\lnot}{\exists}x{\exists}y{\lnot}{\exists}z(x{\neq}y{\land}x{\neq}z{\land}y{\neq}z)
$

And finally, combining the three:

$
(1){\land}(2){\land}(3)
$

I am really not sure.

Thanks in advance

EDIT:

Actually, assuming that I do need to show that there is no case of less than 3 elements (n elements), I would probably need to show that there is no case where there is just one element as well (from 1 until n-1), am I correct?


texts:
This is really a second part to my first question, but I felt that this was different enough from the first part that it merited its own question.

So, using Church numerals, we define

$3 = {\lambda} f. {\lambda}x.f(f(f(x)))$,

and

$4 = {\lambda} f. {\lambda}x.f(f(f(f(x))))$.

We can then add with an expression like

$3\ g\ (4\ g\ z)$

And this reduces to:

$(g (g (g (g (g (g (g\ z)))))))$.

But, of course, this is not how we would define $7$ in the scheme above.  $7$ would be

${\lambda}g.{\lambda}z.(g (g (g (g (g (g (g\ z)))))))$.

Why is it still legitimate to call the application $3\ g\ (4\ g\ z)$ "7" when we can no longer perform functions with it?


texts: IF A is reduced to B and B belongs to NPC then where does A belongs to?

texts:
i came across a question with no proper explnation.
IF A is reduced to B and B belongs to NPC then we cant say anything about A since it can be as harder a NPH and as easier as P.
i know why it is as harder as NHP but i am not able to figure out about P class.

according to me if A > B(A polynomial time reducible to B) and B belongs to NPH then A is as easier as NPC and as harder as NPH.
A cannot belong to P since if A belongs to P then then in polynomial time i can solve P and in additional polynomial time i can reduce the results of A to suffice results of B.but as given B belongs to NPH and thus no polynomial time algorithm exists to solve B. which is contradiction to the assumption of A belongs to P.
can someone explain what mistake am i making?


texts:
In the "Covering Things with Things" paper from Langerman and Morin, they mention the BST-Dim-Set-Cover, which is a FPT algorithm for point-line-cover, at page 666.

The algorithm chooses each point p from a set S and then subdivides it into k-lines.

This can be seen as a special case of set cover. All points (each p belongs to P) are in a cartesian plane, and the algorithm needs to find if they can be covered by k lines (where each line l belongs to L). This image below clarifies it further:

My question is around what is written in the paper linked above at page 666 regarding where is p taken from: At some point during the text it says "Otherwise, the algorithm chooses an element p ∈ S'". However, further down in the algorithm it says "choose p ∈ S" (without the prime symbol).

Is p taken from S or S' (S prime)?

Thanks!


texts: How Does an Operating System/BIOS Determine Physical Addresses of Devices?

texts: So I understand that in every computer, the Operating System, the BIOS, or both will determine the physical addresses of the hardware devices and then translate that into virtual addresses. What I don't get is....how? Is there a special piece of hard drive that contains those addresses? Is there a special assembly instruction or a special sequence of instructions that will return the address? I want to know the low level operations that make this possible. I understand that there are high level libraries written for this but I don't want that, I want to know exactly how it works, not how to make it work but how it works on a low level.


texts:
So the way I understand it, if station A and station B, for example, try to transmit a frame at the same slot, a collision occurs, leading to an attempt at the next slot. But wouldn't the algorithm just repeat itself? The same two stations would try again on the second slot and it would still cause a collision. Also, it means that the first slot would remain unused.

Am I understanding it wrong?


texts: Solutions to synchronization problem need to be executed in critical section

texts:
I was reading about synchronization problems for cooperating processes and i learned that only hardware solutions like test_and_wait() and compare_and_set() are performed atomically at the hardware level and in all other software solutions like mutex, semaphore the code needs to be executed atomically and hence these have to be executed in the critical section themselves.

Does this mean that these software solutions have limited use when compared to the hardware solutions, though it seems that the former are used extensively?


texts: How are all NP Complete problems similar?

texts:
I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps.

Prove that current problem is NP, i.e., given a certificate, prove
that it can be verified in polynomial time.
Take any known NP-complete problem (call "Easy") and reduce all
of it's instances to few instances of given problem (call
"Hard"). Note this is not necessarily an 1:1 mapping.
Prove that above reduction can be done in polynomial time.

All is well here. Is this knowledge right "if you can solve any NP-complete problem in polynomial time, then all NP-complete problems can be solved in polynomial time" ?

If yes, then as per above proof technique, let's say "Easy" problem can be solved in polynomial time, how does that imply "hard" can be solved in polynomial time? What am I missing here? Or is this true, that "hard" problem can be reduced to the "easy" problem too?


texts: Complexity class of Determining Hamiltonian cycle

texts:
I Know that determining Hamiltonian cycle in a graph is NP complete. For the sake of my clarification, I just want to know that whether the problem remains NP complete with following restrictions ?

1) Graph is undirected , and  every node has degree two.

Any help will be appreciated. Thanks.


texts: Can a Non-Deterministic Pushdown Automaton recognize $ \# a^nb^{2^n} \# $ which a TM can?

texts:
$ \# a^nb^{2^n} \# $

such that

• The alphabet of the machine is {, a, b, x}.

• The symbol x will never appear on the input a.

• The contents of the tape at completion may be anything.

• The head begins on the lefthand #.

• n ≥ 0.

I know that a Turing machine could recognize this language. But can a NPDA recognize this language too? I am thinking it can but I do not know how to start proving how/why?


texts: Find a CFG for the set of prefixes of a CFL

texts:
How do i generate grammar for Prefix  of Langauge L, SupposeG=(V,,P,S)is a context-free grammar generating a CFL L then pref(L) is defined as pref(L)={x∈∗ : ∃ y such that xy∈L}.

I understand for Suffix(L) we would do something like this .. Can someone here help me how do we do for the Prefix(L) if L is CFL.

For each variable X of G , add a new variable
X' . (X' will generate the suffixes of the language that is generated by using X as the start variable.)
Whenever X' →YZ is a rule of G , we add two new rules,X' →Y' Z and X' → Z' .
for each variable in G , we add
X' → X and X' → ε
If S is the start variable of G , we let S' be the start variable of G'.
Now the new CFG G' can generate the suffix of A , and hence context-free language is closed under the suffix operation.


texts: This is a basic question, but I'm thinking that $O(m+n)$ is the same as $O(\max(m,n))$, since the larger term should dominate as we go to infinity? Also, that would be different from $O(\min(m,n))$. Is that right? I keep seeing this notation, especially when discussing graph algorithms. For example, you routinely see: $O(|V| + |E|)$ (e.g. see here).


texts: Finding independent set of size n in an undirected graph

texts: Is there an algorithm that, given an undirected graph, finds an independent set of size n (where n is less than or equal to the total number of vertices)?


texts: Determining if a context-free grammar produces even-length strings

texts: Given a context-free grammar, is there an algorithm to determine if the CFG will ever produce an even length string? Or is this undecidable?


texts: Modifying the grammar to include another operator

texts:
I have this grammar for arithmetic expressions

E -> E+T | T

T -> T X F | F     (X is cross product operator)

F -> (E) | a

Now I am  wanting to add the exponential operator ^ to it, it needs to have higher precedence than multiplication and it needs to be right associative.

Would this be correct? Since first we write the steps for lower precedence?

E -> E+T | T

T -> T*F | F   (multiplication)

F -> F^X| B    or is it X -> F^X to make it right associative?

B -> (E) | a

F -> (E) | a


texts: Differentiate between humans and robots using their mouse movement patterns

texts:
I am looking for references that talk about the existence of a general pattern in mouse tracking data of humans when they do a matching game. I am going to use this knowledge to differentiate between humans and the robots trying to play the game as humans.
Does anybody know a reference about the mouse movement pattern of humans?
I would appreciate any advice. Thanks.


texts: I read in some sources that valid formulas are tautologies (valid under every evaluation). In the others, I read that these are formulas that have conclusions true when premises are true. Are these just equivalent definitions because ⊨ P → Q is equivalent to P ⊨ Q?


texts:
The variables $a,b,c \in \{0,1\}$, thus $a^k, b^k, c^k \in \{0,1\}$

I want to pass a query to an oracle that returns the coefficients of each term $(1,a,b,c,ab,ac,bc,abc)$ in the expansion of products such as this one $(1-a+ab)(1-b+bc)(b-bc)$. There could be more variables and more brackets to expand.

Do I require a single FP query to do this or something more?

edit:

Input: $(1-a+ab)(1-b+bc)$

Expand: $a b^2 c - a b^2 - a b c + 2 a b - a + b c - b + 1$

Apply property of idempotence:  $a b c - a b - a b c + 2 a b - a + b c - b + 1$

Simplify: $1 - a - b + ab +bc$

Extract coefficients: \begin{matrix} 1 & 1 \\ a & -1 \\ b & -1 \\ c & 0 \\ ab & 1 \\ ac & 0 \\ bc & 1 \\ abc & 0 \end{matrix}

Question: What is the 'weakest' oracle capable of extracting the coefficients above from the input?


texts: An algorithm to determine probability of one string appearing earlier than another string in an evenly distributed binary sequence

texts:
Given two binary strings of length $n$ and $m$, determine in polynomial time the probability of the first appearance of one string being earlier than the first appearance of the other one in an evenly distributed infinitely long binary sequence.

Edit: I didn't consider my attempts at solving this to be relevant, they are as follows:

I've considered to use a Markov chain and the fact that $P(A_j)$, the probability of absorbtion of the chain in the $j$-th absorbing state, $=(b^{(0)}NR)_j$, where $b^{(0)}$ is the vector of probabilites of the starting state, $N$ is the fundamental matrix of the chain and $R$ is the matrix that describes the probability of transitioning from some transient state to some absorbing state.

I've indexed the chain states by $(i, j)$, where $i$ is the length of the longest prefix of the first string ($s_1$) that matches in the current state, and $j$ is the same for $s_2$.

Absorbing states are $(n, *)$ and $(*, m)$, where $*$ denotes any number, therefore splitting $P$, the transition matrix of the chain, into $Q$ and $R$ is trivial.

The only thing left is to compute $P$ in polynomial time, which is where I'm stuck. I have written this algorithm, but it's not correct:

for i = 0...n
    for j = 0...m
        if i == n || j == m // absorbing state
            P[(i,j)][(i,j)] = 1
        else if s[i+1] == r[i+1] // bits are the same => either in both strings the next bit will match or it will in neither
            P[(i,j)][(i+1, j+1)] = 0.5
            P[(i,j)][(0,0)] = 0.5
        else // bits are not the same => in both cases only one of the bits will match
            P[(i,j)][(i+1,0)] = 0.5
            P[(i,j)][(0,j+1)] = 0.5

The problem with this algorithm is that in case a bit does not match, the matching prefix length may not be zero, for example on sequence $010...$ for the string $011$ the matching prefix length will be $1\rightarrow 2\rightarrow 1\rightarrow\ldots$, instead of $0$, as my algorithm implies.


texts: About a pre-processing step for primal-dual weighted set cover problem

texts:
I was reading the paper titled "Primal-dual RNC approximation algorithms" by Rajagopalan and Vazirani. I have a problem of understanding the Lemma 4.1.1.

They present a dual fitting based algorithm for weighted set cover. First let me set up the required concept to clarify where I am having trouble. Suppose we have $n$ elements ($U$) and $m$ sets ($S$). Each set has a positive weight. Let $E_v$ holds the sets in which the element $v$ is present. Let $\beta =$max$_{v \in U}$ min$_{s \in E_v}$ weight(s). Let also $IP^*$ is the weight of an optimal set cover. It is easy to see, $IP^*\geq \beta$.

Now assume we have an approximation algorithm for weighted set cover. What the paper is saying in the lemma is that you can do a pre-processing before starting the approximation algorithm as follows. You can scan through the sets and add any sets that have weight $\leq \beta/n$. Since there are $n$ elements the additional cost is at most $\beta$. Then they claim that

  Since $\beta$ is a lower bound on $IP^*$, this cost is subsumed in the approximation.
  And this is the statement I did not understand.


texts:
In a flow network, suppose we add constraints of the following type:

The flow entering a vertex $v$ must be at most the flow exiting a vertex $u$.

Is maximum-flow with such constraints still solvable in polynomial time?
Is it possible to reduce it to a standard maximum-flow problem?
NOTE: I found a recent paper that studies network flow with  constraints, however, the constraints studied there are different:

"A negative disjunctive constraint states that a certain pair of arcs cannot be simultaneously used for sending flow"
"A positive disjunctive constraint forces that for certain pairs of arcs at least one arc has to carry flow".


texts: Is the language $L=\{a^nb^m \mid n>2^m\}$ context-free?

texts:
I cannot go on with this exercise:

  Determine whether $L = \{a^nb^m \mid n > 2^m \}$ is context-free.

Let's suppose that $L$ is context-free. According to the pumping lemma, there exists $N > 0$ such that every $z \in L$ of size at least $N$ has a decomposition $z = uvwxy$ such that

$|vwx| \leq N$.
$|vx| \geq 1$.
For all $i \geq 0$, $z_i = uv^iwx^iy$ is in $L$.

Let's use $z= a^{2^N+1}b^N$.

Then
$|z| = 2{^N+1} +N > N$ and $v= a^h$ and $x= b^k$ with $1 \leq h+k \leq N$.

So $z_i = a^{2^N+1}a^{h(i-1)} b^{N-k}b^{k(i-1)}$.

So if there exists $i > 0$ such that $2^N+1+h(i-1) \leq 2^{N+(i-1)k}$, then $z_i \notin L$.

How can I go on to show that $L$ is not context-free?


texts: Can machine learning be used in this scenario?

texts:
I'm keen to learn more about machine learning, as I feel it could be something that might have its uses in my place of work. I write PC software that controls scientific instruments, and one of its functions involves measuring a voltage every 100ms for (say) 10 seconds, then plotting this on a chart in my software. The chart typically consists of a single peak, although its shape will vary depending on how well "tuned" the instrument is.

Using this chart (which keeps plotting over and over again), an engineer will tune the instrument to achieve the best peak shape possible. While there is no such thing as a "perfect" peak, the requirement is to:-

Have a flat top (some noise is normal)
Have (near) vertical sides
Have the peak centred in the chart (on a poorly tuned instrument the peak will be shifted to the left or right).

Tuning of the instrument involves configuring many different parameters in the PC software which sets voltages and pressures within the instrument, all of which can affect the peak shape. Tuning is trial and error, with the engineer trying ranges of values for each parameter, and can take days or even weeks due to the many permutations involved.

I had been wondering if ML could be used to implement an "auto-tune" feature in the software, but I'm struggling to know which ML concepts, algorithms, and so on, I should be considering - and where to start! At the same time I don't want to be accused of trying to find a problem to solve with ML just for the sake of it.


texts: why not just use a random number generator as a hash function?

texts:
I guess at the heart of this is that I don't really understand hash functions.

One article says any function mapping objects to an object of fixed size:

  A hash function usually means a function that compresses, meaning the
  output is shorter than the input. Often, such a function takes an
  input of arbitrary or almost arbitrary length to one whose length is a
  ﬁxed number, like 160 bits.

Why not just use a random number generator to generate the hash keys?  Wikipedia  suggests SHA1 which maps to $2^{160}\approx 10^{48}$ possible outputs has never experienced a "collision".

I was trying to understand why the hash is necessary in a probabilistic counting algorithm:

class LinearCounter():
    def __init__(self, m, h):
        self.array =  [False for x in range(m)]
        self.hash = h

    def add(value):
        self.array(self.hash[ value ]) = True

Is the hash necessary? Why can't we use a random number generator right away?

def add(value):
    self.array(int(m*random.random()))


texts: Merge sort and quicksort recursion tree depth

texts:
1)
I need to determine recursion tree depth for strings composed of 10, 100 and 1000 elements when using merge sort. For the 10 elements one/I can do it on a paper, just drawing tree, but what about 100 or 1000 elements? How do I determine recursion tree depth for them? Is there any pattern that I cannot see? What if someone would ask me for recursion tree depth for a string composed of one million elements?

2)
I need to determine the biggest and the smallest recursion tree depth for strings composed of 10, 100 and 1000 when using quicksort. So it's kind of similar but those could be any strings, so is there even constant number that defines the smallest and the biggest? How to count this?

3)
I need to provide a recursive dependency which value for the given $n$ is the number of recursion tree levels of recursive calls of merge sort for an $n$-element string.


texts: What are recent, high-quality surveys on NLP topics?

texts:
In particular POS tagging, dependency and constituent parsing. This is not really my field of study but I would really like to be able to make informed claims on what precisions current top systems achieve (and what top systems for each task are).

This paper of a (high quality) system (http://arxiv.org/abs/1103.0398) we have used in experiements uses benchmarks from 2000, 2003 and 2005. But I don't know if more recent systems have outperformed those or new benchmark tasks exists.


texts: Is there a formalization of automatic-splicing data structures?

texts:
I'm wondering if there is some formalization, type theoretical analysis, or similar for data structures that automatically "splice" in an associative way. Barring a perfect citation, I'd be interested to know if there are other keywords I should be looking for in this space.

Examples are particularly common in term-rewriting languages, such as Tuples and Matricies in Purelang or Sequence in Mathematica.

I'm also interested in one particularly challenging question with these constructs: How should "quoting" (to prevent splicing) be represented and handled?


texts: Clarifying Practicality and Usage of a DFA's Accepted Language

texts:
I was reading up on DFA's and their accepted languages when I stumbled across this:

Let a DFA $M$ accept the language $L⊆Σ^∗$, DFA $M'$ accepts $P(L)=$ {$w∈Σ^∗|wy∈L$ for some $y∈Σ^∗$}.

Since any $wy$ has to be an element of $L$ in order for $w$ to be an accepted string, and $L⊆Σ^∗$, then wouldn't all states be accepted by $M'$?

For example, for machine $M'$ with the alphabet $Σ=$ {$0,1$}, let $w=01$. Since all values of $y$ also have to be in the alphabet $Σ^∗$, $w$ would have to be accepted. Let $y=10$, $wy=0110$, which is in the alphabet $Σ^∗$. Similarly, let $y=110$, $wy=01110$, which is again in the alphabet $Σ^∗$.

The text mentioned some transition from $M$ to $M'$, but what would the use of $M'$ actually be? How is it any different than, say, $L=$ {$w∈Σ^∗$}? Would they share the same finite-state diagram?


texts: Propose a family of hash functions with $mod p^2$ for some prime number $p$

texts:
I need to define a family H of universal functions $\{0,1, ..., p^k−1\} →\{0,1, ..., p^2−1\}$.
Now based on a similar example I was thinking of something like:
Given some $a= (a1, a2, ..., ak)∈\{0, ..., p−1\}k$, define
$h_a(x)=(a_1x_1+a_2x_2+...+a_kx_k)\ mod\ p^2$ for $x \in \{0,1, ..., pk−1\}$ as we can write x as a sum of digits that represent it in base p. Meaning $x=(x_1,...,x_k)$ where $x_i∈\{0, ..., p−1\}$ and $p$ is some prime number.
Is it a universal family? Because I use $mod\  p^2$ which isn't a prime number.


texts: Termination of deterministic term rewriting

texts:
Consider a simple language:

$$t ::= plus ~ t ~ t ~ | ~ gen ~ t ~ | ~ except ~ N ~ t ~ | ~ N$$

with N constructors plus, gen and except, N being the natural numbers, and $G = \{t_n\}$ a finite, ordered set of terms.

These terms can be evaluated using a small step operational semantics:

$$\frac{G ~ \vdash ~ t_1 \rightarrow t_2}{G ~ \vdash ~ plus ~ t_1 t_3 \rightarrow plus ~ t_2 ~  t_3}$$

$$\frac{G ~ \vdash ~ t_1 \rightarrow t_2}{G ~ \vdash ~ plus ~ n ~ t_1 \rightarrow plus ~ n ~ t_2}$$

$$\frac{}{G ~ \vdash ~ plus ~ n_1 ~ n_2 \rightarrow n_1 + n_2} \\ \text{using the addition on natural numbers}$$

$$\frac{G ~ \vdash ~ t_1 \rightarrow t_2}{G ~ \vdash ~ gen ~ t_1 \rightarrow gen ~ t_2}$$

$$\frac{}{\{t_n\} ~ \vdash ~ gen ~ n \rightarrow except ~ n ~ t_n}$$

$$\frac{G \setminus \{t_n\} ~ \vdash ~ t_1 \rightarrow t_2}{G ~ \vdash ~ except ~ n ~ t_1 \rightarrow except ~ n ~ t_2}$$

$$\frac{}{G ~ \vdash ~ except ~ n ~ m \rightarrow m}$$

The idea is that the stored terms in $G$ might be mutually recursive, but are not allowed to "loop". Hence, everytime, one term is selected from $G$, it is wrapped in an $except$ term that prevents such a loop.

It seems intuitive, that this system (i.e. a function that applies a rule as long as possible) always terminates. But is that so? How does one prove this? I tried to map the evaluation to a CPO, but failed so far.

The problem is proving the supremum of a directed chain: The term might grow and shrink. It may only grow however, when an except node is introduced, which reduces the allowed set $G$. So expansion is clearly limited. Any reduction clearly shrinks the term which is also limited. So I'd need a CPO defined as the product of these two orders that is not defined as usual.

Does anyone have an idea how to solve this?


texts: how to prove that $NP \cap co - NP$ = { S | S such that there exist a Strong Deciding Algorithm for S}?

texts:
i need to prove that and i find it struggle:
given:

for deciding problem S:

a non deterministic algorithm $A(x)$ is strong deciding algorithm if:

$x \in S =>$ fo every run of $A(x)$ returns "Yes" or "Maybe", and there exist run which $A(x)$ returns "Yes"
$x \notin S =>$ for every run of $A(x)$ returns "No" or "Maybe", and there exist run which $A(x)$ returns "No"

now we need to prove i assume with equality between two sets that

$NP \cap co - NP$ = { S | S such that there exist a Strong Deciding Algorithm for S}

thank you,


texts: Complexity class that properly included in DLOGTIME

texts:
Is there any decision problem that is in a complexity class properly included in DLOGTIME? (except $O(1)$, of course)

If there is, can we create complete problems for DLOGTIME? So, can there be reduction by $O(\log(\log n))$ or smaller?


texts: Why cannot we enumerate all Turing machines that have no fixed point?

texts:
The language

$$
L_1 = \{w \in \{0, 1\}^\ast \mid \exists x \in \{0, 1\}^\ast\colon M_w(x) = x\}
$$

($w$ is an encoding of a DTM, $M_w$ is the respective DTM.)

is not decidable, according to Rice's theorem. However, it is recursively enumerable: an NTM simply chooses an $x$ for which the condition is fulfilled non-deterministically.

Consider the very similar language

$$
L_2 = \{w \in \{0, 1\}^\ast \mid \exists x \in \{0, 1\}^\ast\colon M_w(x) \neq x\}
$$

Rice's theorem argues that this is undecidable, but neither is it semi-decidable according to my sources.

Why can't we argue for $L_2$ as we did for $L_1$, stating that an NTM chooses the input $x$ non-deterministically, the condition is fulfilled, $L_2 \in \mathsf{RE}$?

The proof that $L_2 \not\in \mathsf{RE}$ performs the reduction $\overline H \leq L_2$, where $H$ is the halting problem. I understand this proof by reduction, but to me, it seems contradictory to the argument for recursive enumerability I give above.


texts: Regular expression for all binary words avoiding 11

texts:
I am reading a book example on regular expressions and I have a trouble to get why the answer is correct.
"Write a regular expression for the regular language that contains all the strings by 0's and 1's , in which the digits next to 1's , are always 0's"
So , basically , we just need to create a regular expression , that "abandons" '11's (two 1's net to each other)
The answer in the book is:
$$(\epsilon|1)((101)^∗|0)^∗(1|\epsilon)$$
I don't get it: $((101)^∗|0)^∗$ can create a term $(101)(101)$ which is forbidden, can't it? Or maybe we have $1(101)$ by this regular expression, can't we?
I am thinking it should be something like:
$$(\epsilon|10)(1|\epsilon)((01)^∗|0)^∗(01|\epsilon)$$
Update: The folks at math.se answered this question.


texts: Approximation ratio of a greedy grid-cover algorithm

texts:
We're given a $N\times M$ grid, and we want to cover all coordinates in the greedy by rectangles of size $\le k$.

Consider the following greedy algorithm.  At each iteration, it chooses a rectangle of area $\le k$ which covers as many uncovered elements as possible.  If more than one such rectangle exists, it chooses one arbitrarily.

Can we prove a bound on the approximation ratio of this algorithm?

For example, if $M=1,N=6,k=3$ (i.e., we wish to cover a length $6$ line with intervals of size $3$), the optimal (minimizing the number of rectangles in the cover) picks a rectangle covering $[1,2,3]$ and another one covering $[4,5,6]$.

The greedy algorithm, on the other hand, may first choose the interval $3,4,5$, and then proceed with $1,2,3$ and finally $4,5,6$.

The number of rectangles used by the algorithm is $3$, while the optimum is $2$, thus the approximation ratio of the example is $1.5$.

I have a proof that the approximation ratio of the 1D case ($M=1$) is $2$ (and it is tight).

  What is the approximation ratio of the general $N\times M$ grid algorithm?

I'm well aware that it is probably possible to solve the problem optimally in linear time with a different algorithm, but in my application the rectangles are generated arbitrarily (e..g, think of a stores who wish to serve as many customers as possible in a grid) and are not ours to choose.


texts: Efficient algorithm for edit distance for short sequences

texts:
I have an application that needs to compute billions of levenshtein distance between pairs of strings. The strings are short (70 in length) DNA sequences, consisting only of 4 characters. Also it can be assumed that one of the strings is fixed, i.e., we are comparing one fixed string to a billion other strings.

I know that the dynamic programming implementation of the levenshtein distance is $\mathcal{O}(m n)$, would like to know if there are any room for improvement. I found these two algorithms:

$\mathcal{O}(n + d^2)$ algorithm, in which $d$ is the edit distance by  Berghel et al. However I can't make the assumption that $d$ is small so it might not give any advantage
$log(n)^{\mathcal{O}(1/\epsilon)}$  approximation in $n^{1+\epsilon}$ time by Andoni et al. But I have two concerns regarding this:

Is this algorithm also fast in practice?
Does $log(n)^{\mathcal{O}(1/\epsilon)}$ mean the computed edit distance in worst case is $log(n)^{\mathcal{O}(1/\epsilon)}$ times the actual one? In that case it's too much.

Do you know of any other algorithm/idea/approach that might be applicable?


texts: Difference between grammar productions and derivations

texts:
My understanding is that a production is a 'rule' of a grammar which defines how a symbol sequence can be rewritten into another symbol sequence.

A derivation on the other hand is the process of forming a new symbol sequence by following the rules (productions?) of the grammar.

The Wikipedia-page in my language contradicts me here and my English isn't good enough to understand the english one so I would be very thankful for a correction or better explanation of this matter.


texts: Minimum cost subset of sensors covering targets

texts:
I have a dynamic programming problem:

  If I have a set of sensors covering targets (a target might be
  covered by mutiple sensors) how can I find the minimum cost subset of
  sensors covering all targets given each sensor has a cost?

I have thought a lot about this, but I can't reach the recursive formula to write my program. The greedy algorithm does not always provide the correct minimum cost subset. My problem is that sensors overlap in covering targets. Any help?

Example: I have set of sensors $\{s_1,s_2,s_3\}$ with costs $\{1,\frac{5}{2},2\}$ and 3 targets $\{t_1,t_2,t_3\}$. Sensors cover $\{t_1 t_2,t_1 t_2 t_3,t_2 t_3\}$ and I need to get minimum cost subset by dynamic programming. For the above example if I use greedy algorithm I would get $s_1,s_3$ but the right answer is $s_2$ only.


texts: How to known which algorithm is the best for what situation, when sorting numbers?

texts:
Is there some kind of "universal list" of performance of different algorithms in different situations?
I have different databases that save user input (numbers). However some of these sets of numbers are small and some of them are really big (such as the common one). There are negative numbers included.
I remember from when I took algorithms as a course that there are things such as "big-oh notation" and "theta notation", etc. What I am looking for is some way of looking up which algorithm I should use for different un-ordered lists of numbers.
I know that merge sort has the best over all performance with a worst-case time of $n \log n$ however I also know that both insertion sort and quick sort (worst-case $n^2$) sorts better with fewer elements in the given list. There are a few cases of lists being in reverse sort, where can I look up what is the most effective then?
How do I know which of insertion sort or quick sort I should use then?
What is "a small list of numbers that is quicker to sort with quick sort/insertion sort"?


texts:
In the second edition of the book of Cormen "Introduction to Algorithms" appears the following example (in the left part is the residual network while in the right part shows the flow results):

I have a problem understanding the part (c). The augmenting path is $s\rightarrow v_2\rightarrow v_1\rightarrow v_3\rightarrow t$ with a minimum weight of 8. This weight should be added or decreased in the right part of b:

$s\rightarrow v_2$: it was 0 by default, so now it has 8/13

$v_1\rightarrow v_3$: it has 4/12 adding 8 we would have 12/12

$v_3\rightarrow t$, it has 7/20; adding 8 holds 15/20

the problem is in the vertices: $v_1\rightarrow v_2$, for what I see it has only capacity 4 (b right part), so how to put the flow of 8 that it needs the procedure?. I see that at the end we finish up with a $v_1\rightarrow v_2$ with a value of 1/4, but I have my doubts how to get that result.

Is it that because $v_2:v_1$ has only capacity of 4, and I should put 8 of flow, that only 4 units pass through $v_2:v_1$ and the remaining 4 goes back from $v_1:v_2$? In that case it finds a value of 7/10; so it needs only 3 units giving us $v_1:v_2$ equals to 10, and because there is 1 unit remaining that goes from $v_2:v_1$ giving us 1/4?

Is that logic correct?


texts: Build a regular expression to define a regular language

texts:
The language is an infinite set of chains that are defined by the next conditions.

Conditions:

1) The language chains may consist of symbols from the set {1,a,b}.
2) The language chains always start from subchain '1a'.
3) Every languange chain has to include at least one subchain 'aa'.

For example:

1aa, 1abaa, 1aaab, 1aab1a, ... etc.

My current solution is this:

1a ((1+b)* a)* (a (1+b)*)* a (1+b+a)*

My solution seems to pass tests like these:

Allowed chains    : 1aa, 1aaa, 1abaa, 1aaba, 1aabaa, 1aab, 1aaab, 1aaabaaa
Not allowed chains: 1aba, 1abab, 1ababab

But I'm not quite sure if it's still correct. Is it correct?

If not, please offer your solution using only the type of formal language used in my solution.


texts:
What does it mean when one complexity class has another complexity class superscript?

For example, sometimes in papers I see $P^P$ or $P^{NP}$.


texts: Determine the language of the given NPDA

texts:
Thoughts

I am wondering is the language $ab^*$, since $a$ pushes $X$ to the stack and $b$ pops, and if there is an $a$ there has to be a $b$ to get back to the final state?

Also, is it right to say $ab^*$ since there is no rule saying that if the top of the stack is $X$ and the input is $a$ I can push another $X$?


texts: The underlying type theory of HOL/Isabelle

texts: Is there a good source on the type theory of HOL/Isabelle/other HOL-based LCF-style theorem provers?


texts: Non-deterministic Turing machine for $L_1 = \{w\#0^n|w \text{ is a suffix of some $x$ in $L$ with } |x|=n\}$

texts:
Show if L is in NP, then also L1 is in NP

  $$L_1 = \{w\#0^n|w \text{ is a suffix of some  $x$  in  $L$  with } |x|=n\}$$

I know that if L is in NP, then there exists a NTM $M_L$ than accepts $x$, with $|x|=n$. I can use $M_L$ to describe an NTM $N$ for $L_1$. I have a problem by understanding which is the best non-deterministic operation in $N$ to create an $x$ string for $L$.


texts: Proving Progress for STLC with Linear and Unrestricted Types

texts:
In this paper Walker presents an extension of STLC with linear and unrestricted types. The proof of type soundness is left as an exercise to the reader. I encountered difficulty when attempting to prove progress (in a theorem prover):

$$ \vdash (S_1,e_1) ~\Rightarrow~ \textsf{value}{(e_1)} ~\lor~ \exists S_2 \exists e_2.~ (S_1,e_1) \rightarrow (S_2,e_2)$$

The relevant typing and evaluation relations can be found on pages 6-17 of the linked document. If we attempt to prove progress by induction on the typing derivation, we encounter the following problem: there is a typing rule for variables, but variables are not values and the evaluation relation says nothing about variables.

Now adding a variable rule to the evaluation relation is the wrong solution. For example, we don't want to reduce $(\varnothing,\mathsf{un~true})$ to $(x\mapsto\mathsf{un~true},x)$, and the immediately reduce $x$ to $\mathsf{un~true}$ by looking up its value in the store. The two solutions I am considering are (1) adding variables to the set of values; and (2) requiring that terms reduce to variables or can take a step in the statement of the progress lemma. Ideally the correction would reflect the original intention of the author. It is also possible that I am misunderstanding the paper or language.


texts: Complete problem for $\mathrm{QP}$ (quasipolynomial-time solvable languages)

texts:
Question 1: Is it known that $\mathrm{QP}=\cup_{k}\mathrm{TIME}(2^{\mathrm{log}^k(n)})$ has any complete problem?

Question 2: Can this be used to simplify the computational complexity theory at all?


texts: Solving an Interlacing Cords puzzle inside a Truncated Octahedron

texts:
My friend got me this really interesting puzzle

Each node can be slided or docked around the Truncated Octahedron, creating knots and tangles in the middle of the puzzle. The idea is to move the nodes around until there's a bunch of knots and then unravel the knots.

To solve this puzzle, you need to following conditions

No cords can be touching, interlacing or tangled.
Each face must contain nodes of the same color.
The opposite of a face must contain nodes of the same color.

This got me wondering, how would a problem like this be modelled in order have it solved by a computer?


texts: Why is unification so important to inference engines?

texts:
I am learning Automated Theorem Proving / SMT solvers / Proof Assistants by myself and post a series of questions about the process, starting here.

I keep reading about the Unification Algorithm.

What is it and why is so important to Inference Engines?
Why is it so important to Computer Science?


texts: Forward error correction for for long strings of bits

texts:
Let $a$ be a large string of bits that is transmitted over a channel that introduces errors (insertions, deletions or substitutions) where the probability of an error happening is $p=0.01$ for each bit. Suppose also that each type of error has a probability of $1/3$ being chosen each time that an error is introduced to $a$. Let $b$ be the resulting string after transmission.

My question is: Is there a way to transmit $a$ correctly over the channel?

I've thought of using forward error correction, in particular I have considered adding redundancy, using CRC, or using something like Reed–Solomon error correction. However, I'd like to know if there is a simpler more naive way of doing this considering that $a$ and $b$ are just strings of $1$'s and $0$'s and that the probability of an error happening is relatively low.


texts: (Finite Automata) Why the following is a NFA?

texts: The first one seems like a DFA. Could someone explain why this is a NFA?


texts: How a NTM reject an input / How a TM simulates a particular NTM

texts:
I understood that a NTM can say only yes but it doesn't know if the input is a NO instance with a single execution. Furthermore, the NTM can diverges and, at the same time, can decide a language (source: Papadimitrou - Computational Complexity, proposition 7.1). While a TM must converges in a "yes" or "no" answer to decide the same language.
Now, we know that for a NTM that decides a language L we can create a TM that decides L
(theorem 2.6). But suppose that the NTM diverges for some computation. How can the TM treat this case?

[EDIT] Definition (source Papadimitrou, pg 45):
A non-deterministc Turing Machine decides a language L if for any input x, the following is true: x belongs to L iff there is an acceptance path.

This definition admits machines that, instead of rejecting an input, diverge and at the same time decide a language.

Theorem 2.6 (pg 47):
Suppose that language L is decided by a nondeterministic
Turing machine N. Then it is decided by a deterministic Turing machine M.

Proposition 7.1 (pg 141):
Suppose that a (deterministic or nondeterministic) Turing
machine M decides a language L within time (or space) f(n), where f is a
proper function. Then there is a precise Tring machine M', which decides the
same language in time (or space, respectively). O(f(n)).

This last proposition confirms that there is a Turing machine that decides a language and that diverges for some path.


texts: Understanding the algorithm behind day of week calculation

texts:
I came across this algorithm recently to calculate day of the week for any year.

int y0 = year - (14 - month) / 12;
int x = y0 + y0/4 - y0/100 + y0/400;
int m0 = month + 12*((14 - month)/12) - 2;
int d0 = (date + x + (31*m0)/12)%7;
switch (d0) {
    case 1: return "Monday";
    case 2: return "Tuesday";
    case 3: return "Wednesday";
    case 4: return "Thursday";
    case 5: return "Friday";
    case 6: return "Saturday";
    case 0: return "Sunday";
}

How does this algorithm work? I see a lot of magic numbers in calculations above, but its difficult to understand the intuition behind this algorithm