texts: Having a better complexity / adversary argument for finding if a finite automata accepts a palindrome

texts:
Let $A$ be a DFA over a finite alphabet $ \Sigma$. Find an algorithm that indicates if $A$ accepts a palindrome and give the complexity of this algorithm.

Here is my solution:

If we denote $^t A$ the transpose of the finite automaton then in order to see if $A$ accepts a palindrome we need to look at the product automaton of $A$ and $^t A$ and find if this product automaton accepts a word. If yes then this is word is a palindrome.

Finding the transpose of a finite automaton takes $O(|V|)$ where $V$ is the number of transition of our finite automaton. Take the product of $A$ and its transpose takes $O(|V|^2)$. And looking if an automaton accept a word takes $O(|V|^{|S|})$, where $|S|$ is the number of states of our finite automaton. So the final complexity I get for the algorithm I described above is:
$$O(|V|^{3 + 2|S|})$$

Now my question is:

Is it possible to improve the complexity? And is it possible to give a proof (using I guess adversary argument) to prove that there isn't a better algorithm (in the sense of complexity) to find if a finite automaton accepts a palindrome?


texts: Model Counting for Sum of Conjunctive Formulas

texts:
Problem:
Let $X=\{x_1, ..., x_N \}$ be a set of binary variables. Each variable can be assigned to either $0$ or $1$ so there are $2^N$ possible assignments.
Input: We are given a positive integer $C$ and a set of binary functions $F=\{f_1,...,f_M\}$ where each function is defined as a simple conjunction of some subset of $X$. That is, each $f_i \in F$ is defined as $f_i(X) := \prod_{x \in X'}x$ for some $X' \subseteq X$.
Output: The number of assignments to variables in $X$ such that $\sum_{i=1}^M f_i(X) = C$.
Question:
Do you know of a polynomial-time algorithm that solves this problem for a bounded value of $C$?
Any ideas or pointers to references would also be greatly appreciated.
It is OK if the complexity is bounded with respect to e.g. some constant $D$ which could be the maximum size of $X'$, that is, the maximum number of variables in the product of any function $f_i \in F$.
Observations:
When $|X'|=1$, that is, when each function $f_i \in F$ can only have one variable, then the problem can be reduced to the counting version of the subset sum problem and can be solved in $\mathcal{O}(N\cdot C)$ time using an modified version of a dynamic programming algorithm for solving subset sum.


texts: Is w ∈ L(M ) ⟹ ww ∈ L(M) co-semi-decidable?

texts:
Consider the following langugage:

$\qquad L = \{ \langle M \rangle \mid M \text{ TM}, w \in L(M) \implies ww \in L(M)\}$.

I've been asked to decide whether this language is in R/RE/CO-RE. I've proved that the language doesn't belong to R and RE using Rice theorem, but I can't find a formal proof for CO-RE. Any suggestions?


texts: Is FNP = FEXPTIME if and only if NP = EXPTIME?

texts:
It is very well known that if the classes $\sf FP$ and $\sf FNP$ are equal, then also the classes $\sf P$ and $\sf NP$ are equal (see e.g. FNP on Wikipedia).

Is it also true that if $\sf FNP=FEXPTIME$ then also $\sf NP=EXPTIME$?  (See the exponential time conjecture.)  I did find a paper constructing real functions that are in $\sf FEXPTIME$.


texts: Given a subset of numbers $1, \dots, n$, find the minimal subset of numbers $1, \dots, n$ sums of every subset of which cover all sums of first subset

texts:
Given a subset $A = \{a_1, a_2, \dots, a_k\}$ of numbers $\{1, 2, \dots, n\}$, find another subset $B = \{b_1, b_2, \dots, b_t\}$ of numbers $\{1, 2, \dots, n\}$ of minimal size (that is, minimise $t$), that every sum of subset of $A$ can be acquired as a sum of some subset of $B$, in time $O\left(2^{\log^2 n}\right)$.

My first observation was what $B$ is indeed the subset (if some number $x$ occurs twice in $B$, we can only optimise the answer if we replace the second occurrence with $2x$).

Also, maximal answer is of size at most $\log n + 1$, as maximal sum is of order $n^2$ and therefore contains $\log n + 1$ bits in binary, which gives the naive answer $-$ just use powers of $2$ from $0$ to $\log n$, all sums of subsets of $A$ can be easily acquired now.

That said, $O\left(2^{\log^2 n}\right) = O\left(\left(2^{\log n}\right)^{\log n}\right)$, seems like it's some bruteforce of subsets of $A$, but I struggle to come up with something.


texts: Measuring how "balanced" a binary tree is

texts:
I have some binary trees, and I'm looking for a metric to quantify how "balanced" a tree is. I don't have a rigorous definition for "balanceness", but my intuition suggests it's a measure of how close the shape of a tree is to a "fully balanced" tree, or how "skewed" the tree is.

I was thinking a possible metric would be the ratio of the number of nodes in the tree to the number of nodes in a fully balanced tree of the same height. This seems relatively naive though, and I was wondering if better metrics exist to measure how skewed/balanced a tree is.


texts:
I need trees that have the following properties:

Each node in the tree has two values associated with it - a key and an associated opaque data element.
An internal node in the tree has unbounded number of children. The tree reflects a real world hierarchy that is in flux over time - hence the maximum number of children of a given node are not known ahead of time.
There is an ordering defined on sibling nodes that is a function of the keys stored in the nodes.

Allow the following operations to be $O(\lg n)$.

Update operations

merge(tree_1, tree_2) - Destructively consumes tree_1 and tree_2 to create a new tree which contains keys from both input trees. I realize now that this operation is underdefined, I will put more thought into the semantics of the merge.
insert(tree, parent_key, child_key, value) - inserts the given key-value pair into the given subtree rooted at the node pointed to by the parent key.
delete(tree, key) - Delete subtree rooted at node with given key.
update(tree, key, value) - Destructively updates the existing data associated with the given key-value pair.

Query operations

find(tree, key) - returns the value associated with the given key in the given tree.
get_tree(tree, key) - Return a subtree that is rooted at node with given key. The returned tree must a reference and share identity with corresponding nodes in the incoming tree. Modifying any nodes via the returned tree will hence result in changes to the initial tree.
children(tree, key) - Returns sequence of (key, data) of child nodes of node corresponding to key.

Things I looked at before I asked this question - Binary trees, AVL trees, Red Black trees, 2-3 trees and they were not suitable because of fixed degree of internal nodes.


texts: Is it necessary to traverse every letter in the tape of a Turing Machine?

texts: Say I want to make a very simple Turing Machine that accepts only strings that contain one or more a's. Can I simply send have the machine move a HALT state once it reads one a, even if there are many letters after that first a? Or would this be bad practice or unacceptable for a Turing Machine?


texts: The difference between dense graph and sparse one

texts:
How to decide whether the following statement is correct?

O(E log E) and O(E log V) are equivalent regardless whether graph is dense or
sparse


texts: How to prove the language of contractible strings is context-free but not regular?

texts:
How to prove this language is context-free but not regular? I can't figure out it.

A string is contractible if there is a sequence of contractions which result in the empty string, where a contraction is the removal of a sequence of length 2 or more consecutive identical symbols. When a contraction is applied it must contract a maximal length sequence of
consecutive identical symbols.
For example, $abaaababb$ is contractible as witnessed by the following sequence of contractions,
$$ab\underline{aaa}babb \rightarrow abba\underline{bb}\rightarrow a\underline{bb}a \rightarrow \underline{aa}\rightarrow \epsilon$$
Let $L$ be the language of contractible strings over the alphabet ${a, b}$. Prove that $L$ is a context-free language and that $L$ is not a regular language.


texts: Two Minimax AIs playing against each other

texts:
I am trying to have my Minimax AI chess players play against each other.

I was a bit confused about an implementation detail.

Let's call black my first minimax AI chess player that plays first.

white is the other minimax AI that goes second.

My question s about the turn. Should black maximize and white minimize OR should they just try to maximize when at their respective turns, with the evaluation function flipped?

I have thought up of two ways to go about this. I have a feeling that they are doing the same thing, but just wasn't sure whether I am right or the two solutions are in fact doing something different.

First solution:

Instantiate a MinimaxAI object for black and white separately. Make sure that black's evaluation function is the opposite of white. For a simple example, the object black's evaluation function is
number of black pieces on board - number of whites on board.

The white object will have an opposite evaluation function number of white pieces on board - number of blacks on board.

Now, when each object takes turns to call the same get_next_move method, they will both be the maximizing player of the minimax algorithm.

Second solution:

Instantiate one Minimax AI object ai to be used by both the black and the white as they alternate turns. black and white will have the same evaluation function
number of white pieces on board - number of blacks on board

Assuming white always goes first in chess, when white calls ai.get_next_move with an even turn number, it will be given the maximizing player role. On the other hand, when black calls ai.get_next_move with an odd turn number, it will be given the minimizing player role.

(this is what I have so far)

I think both should result in the same behavior, but it is more of a feeling than an educated opinion. Please let me know if my feeling is actually correct or not. A semi-formal reasoning process will be welcome!


texts: What's the real difference between throughput and capacity of a network cable?

texts:
I was preparing a presentation in work on GPON & other optical network technologies using documentation provided by a supplier, and the claim it made was "GPON networks have a capacity of up to 100Tbps".

Instantly that looked odd to me as I know the throughput of the most advanced version of InfiniBand only goes up to 280-290Gbps. I couldn't find any evidence that supported the supplier's claim, only turning up that the throughput of GPON was up to 2.5Gbps. The colleague who had been given the documentation I was working off said that the supplier had claimed that speed was independent of the devices on the network, and that it was limited only by the Optical Network Units (ONUs) and endpoint devices.

That seems a bit ridiculous considering the "data" in an optical cable is a pulse of light. Light travels (in a vacuum) at c, so surely the speed of any fibre-optic network is close to c, and in the same way the speed of electromagnetic wave propagation down a wire is 66 - 99% the speed of light, but I've never heard a CAT5 manufacturer claim their cables can support those speeds.

I brought it up with the supplier rep and he (derisively) let me know that "that's the capacity, not the throughput". I'm aware that to a lot of people the terms are interchangeable, but from a technical standpoint if throughput is the amount of data that can be sent over a network in a specified amount of time, what is capacity?

It would seem like the "capacity" of an optical fibre is "1 flash of light" as that's all it's likely to hold.

NB this question is about the science behind computer (or other data) networks, so I think it belongs here, despite references to particular hardware.


texts: On teaching Kolmogorov complexity with Python and the complexity of composed strings

texts:
The setting of this question is a bit long-winded, but please bear with me.

This fall I will be lecturing a course on mathematical information theory, and on a few lectures we will be discussing Kolmogorov complexity. One of the challenges I face is that most of my students will most likely not be familiar or comfortable with an abstract definition of a Turing machine, and the schedule does not permit a tangent to defining finite automata etc.

My current idea is to replace an abstract Turing machine with Python3, i.e. there will be examples and some exercises where we try to produce various strings with Python3 code (with any extra packages not allowed, basically code golfing). I'm fairly confident that I will be able to deliver the fundamental idea with this, but I do have a concrete problem.

In the book Introduction to the Theory of Computation by Michael Sipser we have some interesting results about Kolmogorov complexity (pp. 237-245) which I would like to go through in as much detail as the setting permits. In particular, I would like to prove Theorems 6.25 and 6.26 which state that "$K(xx) \leq K(x) + c$" and "$K(xy) \leq 2K(x) + K(y) + c$", respectively. The latter result in particular is fascinating, and cannot be improved (much) beyond a limit of the type

$$K(xy) \leq \log(K(x)) + K(x) + K(y) + c. $$

To my understanding the fact that we cannot improve the latter estimate to depend only linearly on $K(x)$ and $K(y)$ is due to the fact that the Turing machine producing the string $y$ needs to be informed how long the printout of $x$ is so that it knows where to continue. (Please correct me if I'm wrong, I'm not a specialist when it comes to Turing machines.)

But now we get to the heart of my problem, namely the following argument I could imagine a student making. Suppose I have two strings, $x$ and $y$, and two Python-programs, call them $P_x$ and $P_y$, producing these string, respectively. It doesn't seem far fetched that however these programs print their output, it would not add to the complexity more than a constant amount to instead first store the output to a variable and then print the said variable:

# Program Px
x = ""
...
x = x + "abc"
...
print(x)

# Program Py
y = ""
...
y = y + "cde"
...
print(y)

Now, having these programs of length $K(x)$ and $K(y)$ we could just append them to the same .py -file after changing the last line in $P_x$ from print(x) to print(x,end=''), which omits the printing of a newline character.

Now I have created a program with complexity below $K(x) + K(y) + c$, contradicting Theorem 6.26. I get the feeling that in this argument I'm actually using the conditional complexity $K(y|x)$ instead of $K(y)$, but I can't quite grasp what is the exact point of error.

  Where is my error and how would it be best explained?

Furthermore, any remarks on the general idea of teaching Kolmogorov complexity via limited Python code golfing are welcome.


texts: Simplify the definition of substitution in Lamdba calculus

texts:
Substitution in untyped Lambda calculus is complicated by variable capture.
Can this boring technical complication be entirely avoided by some restriction on the standard formation rules? Something that prevents the dangerous symbol duplication. If so, how? Otherwise why not?
Alternatively, can the complication be avoided by uniformly alpha-converting every Lambda abstraction of the final composite, to ensure that every binding/bound variable symbol only appears locally (and therefore never as a free variable in the argument of an application term). If so, it seems that the substitution rules could be simplified.


texts: Logic minimization via 2 inputs NOR gates: Is it monotone w.r.t to adding a minterm?

texts:
notation: $x+y:=\mbox{OR}(x,y)$, $\bar x:=\mbox{NOT}(x)$, $xy:=\mbox{AND}(x,y)$, 1:=TRUE, 0:=FALSE.
Let $f$ be a Boolean function of $n$-variables, i.e. $f: \{0,1\}^n \to \{0,1\}$.
minterm:= any product (AND) of $n$ literals (complemented or uncomplemented). e.g, $x_1 \bar x_2 x_3  $ is a minterm in 3 variables
$\mbox{NOR2}(f)$ is the minimum number of 2-input NOR gates required to represent a given function $f$. For instance, $\mbox{NOR2}(x_1 x_2)=3$.

Let $f_1= m_1, f_2=m_2$, where $m_1, m_2$ are minterms that are co-prime (i.e, $f_1+f_2$ can't be minimized further. In other words, $m_1,m_2$ are prime implicants of $f_1+f_2$). For instance, $x_1 \bar x_2 x_3   $ and $x_1 x_2 \bar x_3 $ are co-prime

Then, is the following true?
$$\mbox{NOR2}(f_1+f_2)\ge \mbox{max}\{ \mbox{NOR2}(f_1), \mbox{NOR2}(f_2) \}$$

[i.e, adding two coprime minterms can't yield a 2-input NOR circuit with fewer gates]

I think it is true but I can't think of a proof. Any ideas on how to start proving it?


texts: In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?

texts: Let's say I have a string 0110 and after 011 I reach an accept state (let's call the accept state "q") in an NFA. However, there is no transition mentioned in the diagram from q for the symbol 0. Does this mean the computation dies, or does this mean that the string is accepted?


texts: Average time to solve maze through backtracking

texts:
Given a set A consisting of all possible solvable mazes on an n by n square grid, what is the average running time to solve the mazes in A using a standard backtrack algorithm with no optimizations?

The algorithm checks each ajacent space clockwise for a channel, then visits each channel and either marks it off if it encounters a dead end, or previously covered point, or if it reaches the end point the algorithm completes.

This question was on an exam, and I figured O(n^2) cause there is O(n^2) spaces to visit for each maze, but my prof insisted the correct answer could be O(n log n).

A proof would be greatly appreciated.

Thanks!


texts: Understanding the binary and hexadecimal representations of UTF-8

texts:
Here is a code point: U+091D. The symbol it represents in UTF-8 is झ. In hex the symbol requires three bytes: e0 a4 9d. But it looks like the number 091D requires two bytes. So why do we need three bytes to encode the symbol? Probably due to

  the restriction of the Unicode code-space to 21-bit values in 2003

Please see the beginning of the description section. OK, but why did they restrict the code-space to 21 bits?

I converted e0 a4 9d to binary, and the result is

  11100000 10100100 10011101

Then I converted 091D to binary and got

  00001001 00011101

The two binary results seems to have little in common. So how did 091D become e0 a4 9d?


texts: CFL Closure Properties prove or disprove for the following languages

texts:
I have following statements which I must prove or disprove :

1) Let $L$ be a CFL and $k \in N$ then $L^k$ is also a CFL.
2) $L_1 \subseteq L_2 \subseteq L_3$  are Languages, if $L_1$ and $L_3$ are DCFL, then $L_2$ is also a DCFL

The first one I have no idea how to start or whether it is also a CFL

For the second one I think that this is false, because the CF contains the REG and DCF which means $L_2$ can be a REG-Language or a CFL or DCFL?

Is this right? at least this is how I understand it


texts: How shall I resolve a nonlocal name in a language with deep binding?

texts:
From Programming Language Pragmatics by Scott,

  Figure 3.14 Deep binding in Python. At right is a conceptual view of the run-time stack.
  Referencing environments captured in closures are shown as dashed boxes and arrows. When
  B is called via formal parameter P, two instances of I exist. Because the closure for P was
  created in the initial invocation of A, B’s static link (solid arrow) points to the frame of that earlier
  invocation. B uses that invocation’s instance of I in its print statement, and the output is a 1.

  The catch is that a running program may have more than one instance of an object that is declared within a recursive subroutine. A closure in a language with
  static scoping captures the current instance of every object, at the time the closure
  is created. When the closure’s subroutine is called, it will ﬁnd these captured instances, even if newer instances have subsequently been created by recursive calls.

So basically, the quote tries to explain that the following program (which is the same as the one in the screenshot) prints out 1:

def A(I, P):
    def B():
        print(I)
    # body of A:
    if I > 1:
        P()
    else:
        A(2, B)

def C():
    pass # do nothing

A(1, C) # main program

I don't quite understand the reason being "because the closure for P was
created in the initial invocation of A, B’s static link (solid arrow) points to the frame of that earlier invocation", and "When the closure’s subroutine is called,  it will ﬁnd these captured instances". So I modify the example, and then the new example prints out 2 instead of 1:

def A(I, P):
    def B():
        print(I)
    if I > 2:
        P()
    elif I > 1:
        A(3, B)
    else:
        A(2, B)

def C():
    pass

A(1, C)

Another modified example prints 1:

def A(I, P):
    def B():
        print(I)
    if I > 2:
        P()
    elif I > 1:
        A(3, P)
    else:
        A(2, B)

def C():
    pass

A(1, C)

So how can I know which closure matters when resolving a nonlocal name in a language with deep binding?

Generally, is a closure created whenever a function is passed as an argument to another function?

Thanks.


texts:
I have a graph with N nodes and M edges. It is a single component.

Now I have to delete a single node from graph, deleting that node might split graph into 1,2 or more components. The count of such components is required for each deleted node. Note that only a single node is deleted at any point of time.

I need to do this for all the nodes of the graph in a linear time.

Is this possible in linear time? I am able to do this in O(n^2) by running dfs for each node.


texts: How can I translate this quantified logical expression into english

texts:
I was reading chapter-1 The Foundations: Logic and Proofs from this book.

The chapter gives example of translating English sentence : "There is a woman who has taken a flight on every airline in the world." as follows:

Introducing variables : w for women, f for flight, a for airline
Let P(w,f) : “w has taken f”
Let Q(f,a) : “f is a flight on a.”
Translation : ∃w∀a∃f (P(w,f ) ∧ Q(f,a))

I did understood above. Next it gives example of translating negation of above sentence : "There does not exist a woman who has taken a flight on every airline in the world.", which it solved as follows:

¬∃w∀a∃f (P(w,f ) ∧ Q(f,a)) ≡ ∀w¬∀a∃f (P(w, f ) ∧ Q(f, a))

                            ≡ ∀w∃a¬∃f (P(w, f ) ∧ Q(f, a))

                            ≡ ∀w∃a∀f¬(P (w, f ) ∧ Q(f, a))

                            ≡ ∀w∃a∀f (¬P(w, f )∨¬Q(f, a))

I thought their can be straight approach for this translation instead of going through negation. Anyways though my problem is I am unable to interpret the final translation ∀w∃a∀f (¬P(w, f )∨¬Q(f, a)) in plain English.

"Every woman has either not taken all flights or out of all the flight she has taken are not there on some airline." Is this correct? But if yess, it still does not make me much sense. Anyone?


texts: Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?

texts:
This problem is from  Algorithms, problem 2

The Problem Given two sorted list of numbers $X$[1..$n$] and $Y$[1..n]. we need to come up with a O($log n$) time algorithm to find the median of the 2$n$ lists.'

My question is regarding the case where median($X$) is less than the median($Y$).

Here is the proof that the authors(gave) that any element in $X$ less than median($X$) cannot be the median of the two lists.

    Suppose an element e is in $A$ and e $\lt$ median($X$). Then there will be less than $\frac12n$ elements less than e(in $X$)
    Since e $\lt$ median($X$) $\lt$ median($Y$) there are less than $\frac12n$ elements less than e(in $B$)

Because of 1 and 2, the median cannot be any element in $A$ that is less than median($A$)

I agree with every step in the proof and with that statement. However, here is the diagram of possibilities where the median of the two lists can be

Based off that proof, I understand why all the elements  below the median of $A$ and in $A$ cannot be the median of the two lists. But what justification did author use to eliminate median($X$) as a possibility? It wasn't included in the shaded region.


texts: What does it mean to add up O-terms with different variables?

texts: Is this true? O(n) + O(k) =O(n+k).I have searched for it ,the  answers were quite ambiguous and I couldn't find a good explanation.


texts: If we say L ⊂ {a, b, c}* then is L an infinite language?

texts:
I wonder if we say L ⊂ {a, b, c}* then is L an infinite language?
I think Kleene star makes me think L is an infinite language.


texts: Beating scipy's sparse matrix multiplication

texts:
I develop an application that makes extensive use of sparse matrix operations.

Recently, I found out that scipy takes a lot of time checking matrix sizes and what not, up to the point that the checks take more time than the actual operations. See the posted issue with some metrics here.

So I decided to start the dubious enterprise of making my own sparse matrix library CSparse3.

At the moment, using numba, my library is only a 30% slower than scipy in a (+, *, /, -) test. And it is because of the matrix multiplication. Currently, I am using the algorithm from this book.

I am struggling to find other competitive CSC sparse matrix algorithms that are explained for humans. So I'd be grateful to know about better ones if available (with emphasis in the explained for humans part).


texts:
I am studying parsing, i.e. bottom-up parsing. it is said that there some rules which are used by weak precedence grammar. What does weak precedence grammar mean? What about precedence relation?

Any help will be appreciated. If it is possible, could you give an example. Thanks


texts: Bayes net: algorithm to calculate joint distribution?

texts:
I recently started studying bayesian networks and I am now implementing an exact inference algorithm: enumeration. I am aware of the complexity and inefficiency of this method but I want to fully understand it.

As far as I know there are three basic 'steps':

Use Bayes Rule on query / evidence variables.
Use summation for hidden variables.
Calculate joint distribution.

I've tried a recursive approach as suggested in most documentation of the topic, here's the algorithm I'm using (with python):

'''
bayesnet is an instance of a class that hold a bayes net
queryVars is a list of tuples (varname, boolean) to describe the state of a variable, eg. ('B', True)
evidenceVars is a list of tuples (varname, boolean)
'''
def enumerate_method(bayesnet, queryVars, evidenceVars = []):
    #Check evidence vars to apply bayes rule
    if len(evidenceVars):
        return enumerate_method(queryVars + evidenceVars) / enumerate_method(evidenceVars)
    #Check if there are hidden variables left given the query variables
    if len(bayesnet.hiddenVariables(queryVars)):
        #For every hidden variable
        for hiddenvar in bayesnet.hiddenVariables(queryVars):
            return enumerate_method(bayesnet, queryVars + [(hiddenvar, True)]) + enumerate_method(bayesnet, queryVars + [(hiddenvar, False)])

    #Calculate joint distribution of queryVars?

    return bayesnet.joint(queryVars)

I am still unsure of how to implement the joint distribution calculation. My BayesNet class stores, for each variable, a name, a list of parents and a list of tuples with the probability given its parents. The bayes network is fully described.

I guess I have to use the chain rule, but I have trouble with that as it brings new expressions with evidence variables that I do not have.

Am I moving on the right direction? If so, could you provide a suggestion on how to calculate the joint distribution.


texts: How these two Turing machine problems are different in terms of their decidability?

texts:
I was referring to slide 4 of this, which states following:

  It is decidable whether a given CFG accepts a non-empty language?

Then I was reading Intro to Automata theory book by Ullman et al. It states following:

  Let $L_{ne}$ be the language of all codes for Turing machines that accept atleast one input string.
  $$L_{ne}=\{M | L(M)\neq \phi\}$$
  $L_{ne}$ is not recursive.

Knowing that "not recursive" is same as "undecidable" and the functionality of Turing machine is expressed as a CFG, I feel that the problems in above two statements sound same and the statements contradicts each other in terms of their decidability claims. Thus, one of them must be wrong. However I also feel that I still miss something basic and both of them are non contradictory and equally true. But then what I miss?


texts: which rule can conduct this formula $\log n = O(n^{0.000001})$?

texts:
i am learning this post about Big O, which gives this formula

$$\log n = O(n^{0.000001})$$

why is that?


texts: Power of Turing machines that are not allowed to overwrite the input string

texts:
The question asks what kind of languages (regular, context free) can a Turing machine accept if you are not allowed to overwrite the input string. The initial configuration of the machine is start symbol followed by a blank followed by the input string followed by infinite blanks. The head is pointing at the blank just before the input string.

I think that this machine can perform any operation that an unrestricted Turing machine can because you can first copy the input string on the tape and then proceed with the operation. However, my friend pointed out that you cannot copy the string without overwriting it at some point.

Any thoughts?


texts: Find k maximum numbers from a heap of size n in O(klog(k)) time

texts:
I have a binary heap with $n$ elements.  I want to get the $k$ largest elements in this heap, in $O(k \log k)$ time.  How do I do it?

(Calling deletemax $k$ times yields a $O(k \log n)$ complexity.  I'm looking for $O(k \log k)$.)

The only solution I've come up with so far is the following:

You have 2 arrays. A(largest numbers), B(to analyze).

It's easy to find the largest number, since we already have the heap. We move the maximum number to $A$.
We move the maximum number's children to $B$
We sort $B$
We add the children of the largest number in $B$
Remove the largest number from B (first element of $B$), add it to $A$
Repeat the procedure until there are $k$ elements in $A$

The question here is: do we get a $O(k \log k)$ complexity? we obviously repeat the procedure $k$ times, but does the sorting take $O(\log k)$ time? I guess if the array is already sorted it's easy to insert a new number in $O(\log k)$ time. However, will the length of array B always be less than or equal to $k$?

Can you please confirm or deny my solution? If it's wrong, can you please help me find a solution to this problem?


texts: My algorithm is different from CLRS' -- is it wrong?

texts:
Exercise 2.3-7 from "Introduction to Algorithms" by Cormen et al. Third Edition, states:

Describe a O(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether of not there exist two elements in S whose sum is exactly x.

At first, I had no idea how to solve it since I thought you couldn't access elements of a set by index, but assuming you could, here was my solution:
First off, we sort the set S, and then for every element y in S, we search if x - y exists in S. If x - y exists then we are done, otherwise continue the process until we have looked at all elements in S.
Since we sort at the beginning it's O(n log n) and then we perform a binary search for every element, so total cost would be O(n log n) + O(n log n), therefore O(n log n).
But the solution they give in the Lecture Notes is:

The following algorithm solves the problem:

Sort the elements in S.
Form the set S'= {z : z = x − y for some y ∈ S}.
Sort the elements in S'.
If any value in S appears more than once, remove all but one instance.  Do the same for S'.
Merge the two sorted sets S and S'.
There exist two elements in S whose sum is exactly x if and only if the same value appears in consecutive positions in the merged output.

And they go on to say:

Steps 1 and 3 require O(n lg n) steps. Steps 2, 4, 5, and 6 require O(n) steps. Thus the overall running time is O(n lg n).

So obviously they assume a set is just a regular array (you can access elements by index and the elements don't have to be unique). (And just to clarify my assumption, from the beginning of the book up to this point, they haven't put forth their definition of set, so it was easy to assume they were referring to an actual set).
It seems to me that even though their solution is O(n log n), my solution not only does it reduce the "hidden costs" greatly, it's also much more straightforward than theirs.
(To account for the possibility of repeated elements, nothing needs to be modified since the current y is not inside the searching subarray)
I've checked the published erratas (I know it wouldn't be a mistake per se anyway, but I thought it might've said something there), and there is nothing. So my question is: why is my solution wrong? Is my algorithm incorrect or is it my analysis?


texts: How do I get the NAND gate configuration for full adder from the logic table?

texts:
I'm self-studying, but I've gotten stuck already. If I'm given the logic table for a full-adder or any two-output table, how do I figure out the NAND-gate configuration, preferably methodically? Specifically, given the table:

x y z | 2^1 2^0
0 0 0 |  0   0
1 0 0 |  0   1
0 1 0 |  0   1
0 0 1 |  0   1
1 1 0 |  1   0
0 1 1 |  1   0
1 0 1 |  1   0
1 1 1 |  1   1

How do I find the following set-up:

So far, I've gotten:

x'yz+xy'z+xyz'+xyz=x(yz'+y'z)+xy

xy'z'+x'yz'+x'y'z+xyz=x'(yz'+y'z)+x(y'z'+yz)

I can see the first XOR gate between A and B in the diagram and I can see the yz'+y'z XOR gate, but I'm not sure how to proceed from there.


texts: Overflow of integer counter in distributed systems

texts:
I've just been introduced to Paxos.
There is notion of the of value that is incremented each time a new proposal is send. To provide order for proposals, something like time. What happens when this long or integer value overflows and starts from zero again. The proposed sequence number will become lower than the old one and every proposal will be rejected.

Thank you.


texts: Selecting random element from complement of set

texts:
Let $[n] = \{1, 2, \dots, n\}$. Suppose we have a subset $S$ of $[n]$ of size $k$.
Can we sample one element uniformly at random from $[n] \setminus S$ in $O(k)$ time?
It's okay to use $O(n)$ auxiliary memory assumed to be initialized with zeros, as long as your algorithm can run and clean up back to the initial zero state all in $O(k)$ time.


texts:
Let $L\subseteq\Sigma^*$ be a language, where $\Sigma$ is a set, and let $n\in\mathbb N$.
I am wondering if there is some good terminology for

$L\cap\Sigma^n$.

Of course I could say "the set of words in $L$ of length $n$" but maybe there is some special terminology like "level set of length", "grade", "homogeneous section" or I don't know what.... ?


texts: Efficient way to find key points on spline to approximate it with line strip

texts:
Given a spline, what is an efficient way to find (approximately) the least amount (and position) of key-points to approximate the spline with a line strip, so that the largest distance between the line strip and the spline at any given point is <= d.
Here is a visual example. I'm looking to find a computationally efficient way to find the points in the green circles that I use as beginnings and endings for the lines.

What I thought about is walking along the spline, summing up the traveled distance. As I walk the spline, I test the last position as a key-point candidate. Once the distance traveled on the spline and the length of the line through the key-point candidate deviate by a certain percentage, I use the last key point candidate that was still below that percentage. What I'm uncertain about is first, if there is a more efficient way, and second, deviation in length as a percentage is not really the same as distance (e.g. in cm). If there is a relatively long, relatively straight part of the spline, the length deviation that I might accept, could lead to quite a large distance between the spline and the line somewhere on the way, couldn't it?
[Discussion / Comments]
What's a "line strip"?
For the purpose of this question a line strip is a bunch of connected line segments, like the red strip in the image above.
Do you require that each endpoint of each line segment in the line strip must be on the spline?
No. I just require that the maximum distance between the line segment and the spline segment is <= d. And I want to end up with a small number of line segments. It doesn't need to be the smallest number possible, but it should be reasonably small. The smaller the better. If allowing for a few extra segments prevents me from having to iterate over my solutions for optimization, I'd take that.
Given the difference between the lengths of the curved and straight segments, you can give an upper bound for maximal distance between them
That is not a bad idea! As I stated above, I tried this by giving the deviation in percent of the line-segment's length. But using the absolute deviation in length instead (without converting to percent), does give me an upper bound for the maximum distance. So this would be better than what I used before.


texts: Finding all cycles of length <=5 in a directed graph?

texts:
I was wondering if there's an efficient way to find all cycles of a graph of length <= 5 in a directed graph. I've read up on Johnson's algorithm that takes O((|V|+|E|)(c+1)) time to find all cycles of any length (where c is the total number of cycles), but that might be overkill considering I only need cycles of length at most 5. Is there a more efficient way to do this? The input graph can be pretty large with |V| = 600 and Johnson's algorithm seems to take too long!

[A faster but approximate algorithm would do as well!]

P.S: I found this StackOverflow link too, but the answer has 0 upvotes, so I'm not quite sure.


texts: Hash function orders ships from closest to furthest from the origin

texts:
Suppose we have a circular radar that scans for ships in an area enclosed by $x^2+y^2 \leq z^2$ (a circle).

We wish to design a hash function $h$ such that, we can order the $n$ ships from closest to furtest away from the origin.

We want to have an expected time complexity of this ordering algorithm to be done in $\theta(n)$ time.

Each ship has a coordinate $(x,y)$, and so I want my hash function to be something like $\text{h((x,y)) = small index if close to origin, big index if farther}$.

What would be a hash function and algorithm that can run in expected $\theta(n)$ time?

I think my hash function should be something like the following, taking into account the distance:

$h((x,y)) = \sqrt{(x-0)^2 + (y-0)^2} = \sqrt{x^2+y^2}$


texts: Maximum number of paths which do not use the same edge at the same time

texts:
Given a directed graph, consider the problem of finding the largest number of edge-disjoint paths from a source node $s$ to a destination node $t$. I know this can be done in polynomial time, for example by reducing it to a max flow problem.

The question I am wondering about is a slight variation of this: you can have paths which use the same edge, they just can't use it at the same time. More specifically, suppose we have two paths, the first of which traverses the edges $e^1, e^2, \ldots, e^k$ in that order, while the second traverses the edges $w^1, w^2, \ldots, w^l$, also in that order; then we should have $e^i \neq w^i$ for all $i$. It is perfectly OK, on the other hand, to have e.g., $e^1 = w^2$.

For example, consider the graph $$~~~~~~~~3 \rightarrow 2 \leftarrow 4 \leftarrow 5$$
$$\downarrow$$
$$0$$

The pairs of paths $\{(3,2),(2,0)\}$ and $\{(5,4), (4,2), (2,0)\}$ are considered not to intersect since the common edge $(2,0)$ is traversed at different times.

Thus if we add a source node $s$ with out-edges to $3$ and $5$ and a destination node $t$ with an incoming edge from zero, we will have that there are two paths from $s$ to $t$ with the desired non-intersection property.

On the other hand, if the outgoing edges from $s$ go to $3$ and $4$, only one such path would exist, since the paths $\{(3,2),(2,0)\}$ and $\{(4,2),(2,0)\}$ use the same edge $(2,0)$ at the same time.

This is a very natural setup to consider if you study the problem of scheduling shipments across a network.

My question is: does the problem of finding the largest number of paths between $s$ and $t$ in a directed graph which are non-intersecting in this sense have a name? Has it ever been studied before? I strongly suspect the answer is positive  but I don't know what to google for.

Also, it it known (or obvious) whether it can be solved in polynomial time?


texts: Difference between Memetic and Cultural algorithms

texts: What is the difference between a memetic algorithm and a cultural algorithm? I mean they're both evolutionary algorithms where they select a subset of the population to apply some local search logic. And I think that even their metaphor is pretty similar.


texts: Birkhoff-von Neumann theorem for bistochastic digraphs

texts:
A weighted digraph (with loops) is bistochastic, iff

the weights are non-negative,
for all non-sink nodes, the sum of the edge weights of the out-edges is $1$, and
for all non-source nodes, the sum of the edge weights of the in-edges is $1$.

The Birkhoff-von Neumann theorem for a bistochastic matrix states that a bistochastic matrix is a convex combination of permutation matrices. It would be nice to characterize the bistochastic digraphs with a given underlying digraph in a similar way as a convex combination.

Attempted reduction to the Birkhoff-von Neumann theorem: If the underlying digraph has no source and sink nodes, then we can conclude from the Birkhoff-von Neumann theorem that the convex combinations of the in-degree = out-degree = 1 subdigraphs with n-nodes give all possible bistochastic digraphs (because a $n\times n$ permutation matrix corresponds to a in-degree = out-degree = 1 digraph with $n$-nodes, and only subdigraph can occur in the convex combination since no edge can be canceled out).

If the number of source nodes is equal to the number of sink nodes, then connecting each sink with exactly one source allows to reduce the problem to the previous case (because the weight of the newly added edges can only be 1). But if the number of source nodes is different from the number of sink nodes, then I guess that there exists no bistochastic digraph for that underlying digraph. The weights seem to define a flow on the digraph, so the min-cut max-flow theorem should help.

Even so this reduction seems to work, the case distinctions feel less attractive than the Birkhoff-von Neumann theorem. I would prefer to reduce it completely to the Birkhoff-von Neumann theorem (by connecting each sink with each source?), or reduce it completely to the min-cut max flow theorem (or something similar).


texts: When is currying more efficient in deep neural nets?

texts:
I'm reading a blog post on deep Q-learning, and it contrasts traditional lookup-table-based Q-learning with deep Q-learning:

What I wonder about in this picture is: Why does the deep NN not also take a state and action as input? I assume that this has something to do with computational efficiency. Essentially, in the lower graph, the neural net is in "curried form".

When is it more efficient for the deep NN to have type $S\times A \to \mathbb R$ (as the upper graph), and when is it more efficient to have type $S\to (A\to\mathbb R)$ (as the lower graph)?


texts: If we can simulate $NP$-machines why isn't it trivial that $NP=coNP$?

texts:
I'm looking at some proof that shows $NP^{NP\cap coNP} = NP$.

Let's consider the non-trivial direction. Consider $L\in NP^{NP\cap coNP}$. Then, there's an $A\in NP\cap coNP$ such that $L\in NP^A$.

Since $A\in NP\cap coNP$, there're two machines $M_A$ and $M_{\overline A}$ to decide $A$ and $\overline A$, respectively.

Also, there's a machine $M_L$ to decide $L$ which uses an oracle of $A$.

Let $M$ which acts in the following manner:

Act as $M_L$.
instead of querying the oracle:
simulate the query on $M_A$
simulate the query on $M_\overline A$
write on the result tape the proper result and proceed

I don't understand few things:

How do we simulate $M_A$ and $M_\overline A$ exactly?
If we can do the above then why both $M_A$ and $M_\overline A$ are needed? (just simulate one of them to infer if $x\in A$ or not)
Finally, as a consequence of #2, we could infer that $NP=coNP$

I'd be glad for clarifications since this questions bothers me a lot and clearly, I'm missing something crucial of how those machines are simulated.


texts: Proving that $\{0^n 1^{n^2} \mid n \in \mathbb{N}\}$ is not context-free

texts:
How can I prove that $\{0^n 1^{n^2} \mid n \in \mathbb{N}\}$ is not a context free language?

I tried to prove it using the pumping lemma, but I don't know how to deal with the case when $vxy$ contains both $0$ and $1$.


texts:
So I have a system of equations where varibles range over $\{0,1\}$ and the only operation is logical or ($\lor$). Each equation is of the one of two forms

1) $a = b \lor c$

2) $1 = a \lor b$

where a, b ,and c are all positive literals. No negations occur anywhere in these systems of equations.

We say $(x_1, ..., x_n) \le (y_1, ..., y_n)$ if $x_i \le y_i$ forall $i$.

I'd like to find all minimal solutions to these systems efficiently. I can reduce them to SAT by treating $=$ as $\leftrightarrow$ and solving the corresponding sat problem but it seems like this might be a subset that is more efficiently solvable.

Is there an efficient algorithm to solve this problem? Does it belong to some efficiently solvable subset of SAT? is it close to an efficiently solvable subset?


texts:
Suppose for each positive integer $N$, we have a graph $G_N$ with $N$ vertices labelled $1$ to $N$ (so $\log N$ bits are required to specify a vertex). Suppose we have a PSPACE algorithm to determine whether two given vertices in $G_N$ are adjacent (ie the space used is $P(\log N)$ for some polynomial $P$). Consider the following decision problem:

  Given integers $N,M$ and vertices $a,z$ in $G_N$, is there a path of length $\leq M$ from $a$ to $z$ in $G_N$?

(the size of the input is $3\log N+\log M$ bits). We can answer this problem using the following recursive algorithm:

def exists_path(N,M,a,z):
  if M == 0: return a == z
  if M == 1: return are_adjacent(N,a,z)
  for b = 1 to N:
    if exists_path(N,M/2,a,b) and exists_path(N,(M+1)/2,b,z): return True
  return False

The recursion depth is $\log M$, so the space used is $(3\log N+\log M)\log M+P(\log N)$. In particular the problem is in PSPACE. Since IP=PSPACE, there must be an IP algorithm for this problem. In theory I can follow the proofs on wikipedia to encode the problem as a TQBF problem... but I doubt the result will be pretty.

  Is there an explicit IP algorithm for this problem?

I'm happy to assume the adjacency problem is actually in P if it makes things simpler.

Note that we can't just treat the adjacency algorithm as a black box. Indeed fix $k\in(0,1)$ and consider two possible adjacency functions:

def are_adjacent1(N,a,z):
  return z == a + 1
def are_adjacent2(N,a,z):
  return z == a + 1 and a != ceil(k*N)

These represent graphs $G_N,G_N'$ where $G_N$ is a path graph and $G_N'$ is the same minus a single edge. Now hand are_adjacent1 to an honest prover and are_adjacent2 to an honest verifier. Since the verifier can only make $O(\log N)$ calls to the adjacency function, with high probability it will never check the single missing edge, and be convinced that vertices $1$, $N$ are connected in $G_N'$, which is false.


texts: Why are non-deterministic Buchi automata factorially succinct when compared to deterministic Rabin Automata?

texts:
I am trying to demonstrate the following idea without success.

  There are infinitely many $n \in \mathbb{N}$ such that: There is a
  non-deterministic Buchi automata of size $n$ such that a deterministic Rabin Automata
  accepting the same language has at least $n!$ states.

Any help would be appreciated


texts: reduction from the problem "accepts-empty string" to "language of empty string"

texts:
9.9. Construct a reduction from Accepts-$\lambda$ to the problem Accepts-$\{\lambda\}$: Given a TM $T$ , is $L(T) = \{\lambda\}$?

The question is from Martin's Introduction to Languages and Theory of Computation.

I know how reductions work though I am unsure of several things. It's easy to see that if the inner machine (computing "accepts-$\{\lambda\}$") accepts then the outer must also accept, but it is not clear that the other goes as well. How do I ensure this?


texts: AVL Tree or HashTable for storing relatively big data?

texts:
I have been looking to implement a data structure for my project. I came across AVL tree and Hash Table. As I am a beginner so I'm in dilemma what data structure I use for large data. The main operation will be mostly searching through the database efficiently.

AVL Tree seems to be very good option to store around 120000 entries(object) of data and keep the search time to O(logn), however I stumble upon a perfect hashing concept. It states it expected the search time is constant O(1), if collision occur then it would use secondary hash function that will still have access time of O(1) if I'm not mistaken.

perfect hashing function according to Introduction to Algorithm by Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stien is :-
h(k) = ((3k + 42) mod 101) mod size(number of enteries)

Data that I'm storing is from text file, converting each line into an object. All those objects will be inserted all at once in data structure. After that main operation I have to use is search through the data structure.

Bus -> street1 -street2- street3- destination, this line would be converted into an object. So search would be like return the route bus1 took to reach destination5.

Any suggestions which one would be more reliable and efficient for time and space complexity?


texts: Demonstration that every finite set is computable

texts:
What is the best demonstration that show that "Every finite set is computable"?

thanks


texts: Closure of Turing-recognizable languages under homomorphism

texts:
I've proven that the  Turing-recognizable languages are closed under concatenation and I need to show that they are closed under homomorphism.

But what's really the difference? Doesn't closure under concatenation imply homomorphism as well? Or perhaps I misunderstand what homomorphism means when talking about Turing-Recognizable languges?


texts: Why maximum-matching algorithm falls into the category of fill-reducing algorithms?

texts:
My understanding is that "maximum matching" (or "maximum transversal") are algorithms to pre-order matrix to increase the numerical stability. In Timothy Davis' book Direct Methods for Sparse Linear Systems, 2006, however, this algorithm is put in Chapter 7 which is titled "Fill-reducing ordering". In his more recent paper A survey of direct methods for sparse linear systems, 2016, maximum matching was also placed in section 8 which is titled "Fill-reducing orderings".

So far, my had an impression that reordering algorithms can be categorized into 3 classes:

for numerical stability: maximum transversal, etc
for fill-reducing: AMD, etc
for work-reducing or parallelism-increasing: BTF, BBD, etc

I have problems in understanding putting above 3 classes into a single category called fill-reducing...


texts: How to implement minimization of maximum regret?

texts:
We run a report, but for one of our big clients, it is taking too long. There is a loop where it loops for a list and fetches it upstream 1by1. We're making this a bulk operation now, but some items in the list might be invalid and upstream don't tell us which. I now need to silently handle the failures and remove them from the list and send the request again. I figured the best way to do this is to split the list and try again with a recursive function.

Having looked at the 2 egg problem, I wish to do the same here. I wish to minimize the number of requests to be made. That problem seems to use some quadratic function, I'm not familiar with those things or algorithms. Any help or ideas on how to implement this?


texts: Route planning in public transport application

texts:
This is a cross-post of this StackOverflow question, (I'm not aware of linking questions between StackExchange sites). You can ignore the part about programming.

I'm making a journey planner (or a general timetable application) for all the public transport in my country (bus/train/air).

The state of the project is at midpoint, now I'm having a bit of a hard time getting the more difficult part of the application done.

Currently, I have all the stops, routes and departure/arrival times.

When there are direct connections between two points, all is fine, I can get the trips for a chosen day. The hard part is getting a complete journey when there are no direct lines.

Say the user wants to travel from city A to city D, but because there are no direct lines between those cities, he needs to pass through city B and city C.

How can I get the optimized routes and transfers for this situation?

My ideas so far a gravitating towards using a graph, but in that case I need a Time-Dependant Directed Weighted Multigraph, and I really have no idea at the moment how to implement the Time-Dependant part.

Getting just the route can be done by using Dijkstra, A* or Floyd–Warshall algorithms , but because there are departures at different times, I'm not sure how will this be implemented, to get the optimal solution. I need to take into consideration the duration of a segment (A to B, B to C), waiting time for the transfer, maybe the distance too.

Just to clarify, I don't need a single result. I want to get a daily list of all departures from city A that can get the user to city D, with transfers if needed.

Basically, what I'm trying to get is something like this (taken from Bulgarian Railways, or for that matter, whichever railway site), a list of all departures for a chosen day going from Sofia to Kystendil making transfer in Radomir if needed:

If I'm not clear enough, please ask.

I know that this is done so many times (almost any train website has the solution), but I don't know by which terms to even search.

So, my question is: can someone give me guidance how this type of problem is solved?

Or at least by which terms should I search for ideas and how should it be done.

Maybe some suggestions for other sites in the StackExchange network.


texts: I'm interested in how  does cpu read 32 bit word from memory .If the processor has 32 bits of address space then it can  address 4,294,967,295 locations  (or 4 gb) Does this mean that each location has 32 bits.?


texts: Is this a reduction from decision problem to non-decision problem?

texts:
Notations :

AUT$(X)$ (where $X$ is a graph) is the group of automorphisms of the graph $X$

$G=\langle A \rangle $ means group $G$ is generated by set $A$.

$G_{\{\Delta\}}$ is the set-wise stabiliser of $\Delta$

STAB

Input : $A \subseteq \text{Sym}(\Omega)$ and $\Delta \subseteq \Omega$

Find : Generator of $\langle A \rangle_{\{\Delta\}} = \{g \in \langle A \rangle \mid \Delta ^ g = \Delta\}$

ISO

Given : $X_1 = (V,E_1)$ and $X_2 = (V,E_2)$

Find : Is $X_1$ isomorphic to $X_2$?

Claim : ISO $\le_{P}$ STAB ( polynomial time reduction )

Proof : Take disjoint union $X=X_1 \cup X_2$ and note that
AUT$(X) \le \text{Sym}(V) =G$
$G$ acts on the set $V \choose 2$ i.e. set of all unordered pair of vertices.
 Clearly $E \le$ $V \choose 2$ and AUT$(X) = G_{\{E\}}$ under the above group action.

  Question : Is this a polynomial time reduction from decision problem to non-decision problem? Please note that It is possible that I may have misunderstood the reduction

Reference : Poly time computation in groups by E.M Luks  See Page no 3


texts: Meaning of complexity of a computational problem

texts:
If I understand correctly, the complexity of solving a computational problem is defined in terms of which instance $I$ of the problem, what size $n$ of the problem instance, and what algorithm $A$ for solving the problem instance.

Is the complexity of the problem at a given size $n$ of the problem instance defined as
$$
\min_A \max_{I\in \{\text{instances of size }n\}} \text{complexity}(A,I,n)?
$$
Note that the solution to the above optimization $A^*(n)$ and $I^*(n)$ are both functions of instance size $n$.

Or is the complexity of the problem defined for some same algorithm for all the problem instances and all sizes of the problem instances?

Or is the complexity of the problem defined for some same instance for all the algorithms that solve the problem and all the problem instance sizes?


texts: What is the state-of-the-art in machine translation on Chinese/CJK?

texts:
Sorry for my unfamiliarity with the field. Hopefully this question is on-topic here.

Currently the machine translation from western European languages to English is arguably quite robust, with Google Translate able to quite accurately translate articles on Wikipedia or news site. However, it seems to me that the translation between Chinese/Japanese and English is still quite off: Google Translate is frequently unable to produce a reasonably coherent/meaningful translation for even just one Chinese/Japanese sentence.

It gets me wondering, is the state-of-the-art in CJK machine translation still much off the pace compared with European languages? Or is it just that some research advances haven't been applied to the industry yet? What is the current status of the cutting-edge researches on this field, e.g. novel translation models/improvements on precision rate. Where should I go to look for more information?


texts: Recursion Time Complexity (Half n' Half)

texts:
This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity:

Input: string $s = s_1,\ldots,s_n$, integer $k$
Go over all symbols $s_1,\ldots,s_n$, one by one
For each symbol $s_i$, check whether it appears less than $k$ times in $s$
If all symbols appeared at least $k$ times, return $n$
Otherwise, let $i$ be the first index such that $s_i$ appears less than $k$ times
Call the procedure recursively on $s_1,\ldots,s_{i-1}$ and on $s_{i+1},\ldots,s_n$, and output the maximum

Here is a C++ implementation:

int longestSubstring(string s, int k) {
        for (int i = 0; i < s.length(); i++) {
            if (count(s.begin(), s.end(), s[i]) < k) {
                string left = s.substr(0,i);
                string right = s.substr(i+1,s.size()-1);
                return max(longestSubstring(left,k),longestSubstring(right,k));
            }
        }
        return s.length();
    }

The count method runs in $O(n)$.

I'm new to asymptotic complexity, but from what I understand, "half n' half" recursion has time $T(n) = 2T(n/2)+f(n)$ where $f(n)$ is the time the rest of the execution takes. At this point, we'd induct, and get a general pattern. Then, given that we usually know $T(0)$ and $T(1)$, we can get an expression in $n$, which would be our time complexity.

Now, my problem is that my implementation doesn't split the string into exact halves (in the same way a BST traversal splits the input in halves, for example), so I can't really write $T(n/2)$, correct? Are $T(0)$ and $T(1)$, $O(1)$ and $O(n)$ respectively?

Is there, perhaps, a faster way to solve this problem? Leetcode says it runs in 0ms, but I find that dubious. It takes a longer time to execute than one of the highest upvoted Python implementations, which is supposedly $O(n)$.


texts: How can I tell if my edge is border or interior?

texts:
I have an arbitrary collection of nodes connected by edges. I am trying to find a good way to tell if an edge/vertex is on the border or not.
The red nodes and blue lines are considered on border. Black lines and black nodes are considered interior.

All nodes are fixed to points on the Cartesian plane. It is a planar graph (no edges will cross over each other. They will intersect only at a node). Always one graph / connected shape in total (as opposed to multiple independently connected components).


texts: Parsing arbitrary context-free grammars, mostly short snippets

texts:
I want to parse user-defined domain specific languages. These languages are typically close to mathematical notations (I am not parsing a natural language). Users define their DSL in a BNF notation, like this:

expr ::= LiteralInteger
       | ( expr )
       | expr + expr
       | expr * expr

Input like 1 + ( 2 * 3 ) must be accepted, while input like 1 + must be rejected as incorrect, and input like 1 + 2 * 3 must be rejected as ambiguous.

A central difficulty here is coping with ambiguous grammars in a user-friendly way. Restricting the grammar to be unambiguous is not an option: that's the way the language is — the idea is that writers prefer to omit parentheses when they are not necessary to avoid ambiguity. As long as an expression isn't ambiguous, I need to parse it, and if it isn't, I need to reject it.

My parser must work on any context-free grammar, even ambiguous ones, and must accept all unambiguous input. I need the parse tree for all accepted input. For invalid or ambiguous input, I ideally want good error messages, but to start with I'll take what I can get.

I will typically invoke the parser on relatively short inputs, with the occasional longer input. So the asymptotically faster algorithm may not be the best choice. I would like to optimize for a distribution of around 80% inputs less than 20 symbols long, 19% between 20 and 50 symbols, and 1% rare longer inputs. Speed for invalid inputs is not a major concern. Furthermore, I expect a modification of the DSL around every 1000 to 100000 inputs; I can spend a couple of seconds preprocessing my grammar, not a couple of minutes.

What parsing algorithm(s) should I investigate, given my typical input sizes? Should error reporting be a factor in my selection, or should I concentrate on parsing unambiguous inputs and possibly run a completely separate, slower parser to provide error feedback?

(In the project where I needed that (a while back), I used CYK, which wasn't too hard to implement and worked adequately for my input sizes but didn't produce very nice errors.)


texts: Showing that the set of DTMs that run forever is not Turing-recognizable

texts:
The language A, that is all DTMS that run forever on input.

Would this not just be the HALT problem?

Therefore no reduction or proof is necessary, other then stating that?

ANSWER FOUND:
I think i have it, if it was Turing Recognizable, then it would be possible to determine when HALT should reject and therefore HALT would be decidable. Since it is not-decidable, then A must be not Turing Recognizable.


texts: If I have two Turing machines A and B, and I want to use an output of A as an input to B, how is it going to work? Can I just run A, keep the input tape, and then run B (without affecting the number of states A and B? Or do I have to combine an halting state of machine and an initial state of the other machine?


texts: Maximum number of similar groups of a given size that can be made from a given array

texts:
I am given an array of numbers, not necessarily unique, and the size of a group. Let the array be denoted by $B$ and the size of the group be $A$.

I need to find the maximum number of groups with the exact same contents and of size $A$ that can be made from the elements of $B$. Once an element is used in a group it is exhausted. A group can have more than one element with the same value as long as the element is still available in $B$.

Example:

If the input array is $\{1, 2, 3, 1, 2, 3, 4\}$, and the group size is $3$ the maximum number of groups that can be made is $2$, which are $\{1, 2, 3\}$ and $\{1, 2, 3\}$.
If the input array is $\{1, 3, 3, 3, 6, 3, 10\}$, and the group size is $4$ the maximum number of groups that can be made is $1$, which is $\{1, 3, 3, 3\}$.

What I have tried so far, is to frame some equations ( given below ) but after that, I am struggling to come up with an algorithm to solve them.

Let $F_1$ be the frequency of the element $B_1$, $F_2$ be the frequency of the element $B_2$ and so on till $B_n$, where $B_1 \dots B_n$ are distinct elements from the array $B$.

Now I need to choose $n_1, n_2, \dots n_i$ such that

$n_1 + n_2 + \dots + n_i = A$
$k\cdot n_1 \leq F_1\text{ , } k\cdot n_2 \leq F_2\text{ , }\dots \text{ , }k\cdot n_i \leq F_i$
$k$ is the number of groups and we need to maximize it.

Length of $B$ can be as large as $10^5$ and $A$ can also be as large as $10^5$.

Please help me find a greedy or dynamic approach to the problem.


texts: Why is binary search using this weird thing to calculate middle?

texts:
I noticed that in many books calculation of midpoint for binary search uses this:

int mid = left + (right - left) / 2;

Why not use

int mid = (left + right) / 2;

instead?


texts: Show that if $\mathcal{H}$ is PAC learnable in the standard one-oracle model, then $\mathcal{H}$ is PAC learnable in the two-oracle model

texts:
This is a question $9.1$ from Understanding Machine Learning Chapter 3. It goes like this:

Consider a variant of the PAC model in which there are two example oracles: one that generates positive examples and one that generates negative examples, both according to the underlying distribution $\mathcal{D}$ on $\mathcal{X}$. Formally, given a target function $f : \mathcal{X} \to {0,1}$, let $\mathcal{D}^+$ be the distribution over $\mathcal{X}^+ = \{x \in \mathcal{X}: f(x) = 1\}$ defined by $\mathcal{D}^+(A) = \frac{\mathcal{D}(A)}{\mathcal{D}(X^+)}$, for every $A \subset \mathcal{X}$. Similary $\mathcal{D}^-$ is the distribution over $\mathcal{X}^{-}$ induced by $\mathcal{D}$.

The definition of PAC learnability in the two-oracle model is the same as the
standard definition of PAC learnability except that here the learner has access
to $m^{+}_{\mathcal{H}}(\epsilon, \delta)$ i.i.d. examples from $\mathcal{D}^+$ and $m^{-}_{\mathcal{H}}(\epsilon, \delta)$ i.i.d. examples from $\mathcal{D}^{-}$. The learner’s goal is to output $h$ s.t. with probability at least $1-\delta$ (over the choice of the two training sets, and possibly over the nondeterministic decisions made by the learning algorithm), both $L_{(\mathcal{D}^+,f)}(h) \leq \epsilon$ and $L_{(\mathcal{D}^−,f)}(h) \leq \epsilon$

I am trying to prove that if $\mathcal{H}$ is PAC learnable in the standard one-oracle model, then $\mathcal{H}$ is PAC learnable in the two-oracle model. My attempt so far:
Note that $$L_{(D,f)}(h) = \mathcal{D}(\mathcal{X}^+)L_{(\mathcal{D}^+,f)}(h) + \mathcal{D}(\mathcal{X^{-}})L_{(\mathcal{D}^-,f)}(h).$$
Let $d = min \{ \mathcal{D^+}, \mathcal{D^-}\}$, then if $m\geq m_\mathcal{H}(\epsilon d, \delta)$, then it is clear that:
$$\mathbb{P}[L_{(D,f)}(h)\leq \epsilon d] \geq 1-\delta \implies \mathbb{P}[L_{(D^+,f)}(h)\leq \epsilon] \geq 1-\delta$$
And,
$$\mathbb{P}[L_{(D,f)}(h)\leq \epsilon d] \geq 1-\delta \implies \mathbb{P}[L_{(D^-,f)}(h)\leq \epsilon] \geq 1-\delta$$
So we know that if we have $m\geq m_{\mathcal{H}}(\epsilon d, \delta)$ samples drawn iid from $\mathcal{D}$, then we can guarantee $\mathbb{P}[L_{(D^+,f)}(h)\leq \epsilon] \geq 1-\delta$ and   $\mathbb{P}[L_{(D^-,f)}(h)\leq \epsilon] \geq 1-\delta$.
How do I choose $m_{\mathcal{H}}^+(\epsilon, \delta)$ and $m_{\mathcal{H}}^-(\epsilon, \delta)$ such that if we have $m^+ \geq m_{\mathcal{H}}^-(\epsilon, \delta)$ samples iid according to $\mathcal{D}^+$ and $m^- \geq m_{\mathcal{H}}^-(\epsilon, \delta)$ drawn iid according to $\mathcal{D}^{-}$, then we can guarantee $\mathbb{P}[L_{(D^+,f)}(h)\leq \epsilon] \geq 1-\delta$ and   $\mathbb{P}[L_{(D^-,f)}(h)\leq \epsilon] \geq 1-\delta$?
When is drawing $m^+$ samples according to $\mathcal{D}^+$ and $m^{-}$ samples according to $\mathcal{D}^-$ the same as drawing
$(m^+ + m^-)$ samples according to $\mathcal{D}$?


texts:
Call two proper graph colorings equivalent if one can be obtained from the other by a permutation of the colors.
In other words, they are the "same" coloring.

I'm interested in finding proper non-equivalent colorings.
Of course, the decision problem of determining whether or not there is such a non-equivalent coloring given one is NP-complete.

Are there FPT, approximation, etc. algorithms for finding such a coloring if one exists?
I am currently running a randomized greedy coloring algorithm, which does often succeed in finding a proper coloring - however, I am unsure of when it actually produces a non-isomorphic one.

If it is helpful, I'm working with graphs which are essentially $k$-trees.


texts: Time complexity of checking whether a string exists in a HashSet

texts:
From what I know hash sets generally have complexity of $O(1)$ (unless the hash function is bad, but let's just ignore that for this question). However, sets need to either read the full data so as to make a hash function that's guaranteed to return a unique result for every input or they need to make a comparison to make sure the data is the same otherwise. Doesn't that mean that the complexity for strings should be $O(m)$, where $m$ is the length of the string, at least if we accept that these strings can get arbitrarily large? Is there something I do not understand?
The reason I'm asking is because I solved a problem with a trie and the provided solution was solved with a set (that was the only difference), but it assumed that arbitrarily large strings can be found to exist or to not exist in a set in $O(1)$ time. The problem is to find which words in a set of words can be formed using other words in the set (words can be used multiple times) — for example in "a", "bc", "cd", "acd", "abcd", only "acd" can be formed using other words, though I don't think the specific problems matters much.


texts: Modify one element and find out which surounding elements are affected

texts:
I want to know if there is an algorithm which does the following:

Imagine you have a point cloud and the points affect each other but the action
from each point to an other is only valid in some radius around this point (locally).

Now remove one point and the local configuration changes.

How is the cheapest way to determine which points are affected from this removement?


texts: $(Q\to R)\wedge (R\to Q)$ converting to sentence

texts:
Well, I am following this video lecture (MOOC) and I came across this quiz where I have to convert $(Q\to R)\wedge (R\to Q)$  to sentence.

$Q$: "I will go to town"

$R$: "I have time"

My answer to $(Q\to R)\wedge (R\to Q)$  is

"I will go to town ONLY IF I have time AND I have time ONLY IF I will go to town".

Whereas, the professor teaching in video gave following answer:

"I will go to town ONLY IF I have time AND IF I have time I will go to town".

I don't get the answer given by professor because it changes the meaning of sentence after 'AND'.

NOTE: Further professor explain that this can be converted to equivalent "If and Only If", but my concern is not on equivalence. I understand that part.

Thank you in Advance!


texts: Abstract Syntax Tree of Pure Lambda Calculus

texts:
I was wondering if anyone had any good references or book recommendations that cover abstract syntax trees (ASTs). Specifically, I am interested in the abstract syntax trees of different evaluation strategies (call by value vs. call by name) of the pure lambda calculus. I would like to be able to draw the AST of some pure lambda calculus expression such as
$$and \, true \, false = (\lambda a. \lambda b. a \, b \, (\lambda t. \lambda f. f))(\lambda t. \lambda f. t)(\lambda t. \lambda f. f).$$

I would like to know if/how evaluation strategies affect the structure of ASTs, or how order of operation is reflected in the AST of an expression. This seems trivial for any pure lambda calculus interpreter; so perhaps there is some AST generator out there somewhere? I did some searching on Google but found nothing.

I think if I could just get some practice with the AST representation of some non-trivial functions in any language, I will be okay.


texts: How to do product construction with 2 DFA which has dead state

texts: I have been trying to do a product construction(intersection) with 2 DFA which has dead states, but I'm stuck at the transition table with a confusion that,what should I do with dead state. Should I also combine the dead state with other states?


texts: Is this the right way to convert a negative floating point number in binary using two's complement method?

texts:
I'm a cs student and i've just started learning about binary arithmetic.I have to do this homework assignement to get prepared for exams..I'm having some trouble figuring out how to convert a negative floating point number in binary system....I was thiking about IEEE-754 representation but i must use only two's complement method...other than that i'm not really sure if my calculations are right ...I'm really confused.

So the exercise is:

1.Convert a=-9, b=+3.75, c= -1.25, d=+10.2 in binary using two's complement representation.For integer part you must use the minimum number of bits and for the fractional part only 4 bits.

2.Convert the above numbers in signed magnitude representation (in binary)

3.Calculate a-a , b+c , c+a using two's complement of question (1)

my solution:

1.9 as unsigned int in binary: 1001 so +9 is : 01001

-9 is : inversion of bits and then add 1 so : 01001 --> 10110+1-->10111

so a=10111

+3.75: 3 is 11 so +3: 0011 and 0.75: 0.11

together--> 0011.11 is this right?
I think it should be 11.11 cause we want the minimum bits

b=0011.11

-1.25 : 1 is 1 in binary so +1: 0001 and 0.25 is : 0.01

together --> 0001.01

(Again i think it should be 01.01 or 1.01 )

then i invert the bits so 0001.01 --> 1110.10+0.01--> 1110.11

c=1110.11

Is this how we do it?

+10.2 : 10 is 1010 in binary so +10: 01010 and 0.2 is : 0.0011

together--> 01010.0011

d=01010.0011

2.Signed magnitude representation

-9  : 10110

+3.75 its the same : 0011.11

-1.25 : ????

+10.2 its the same : 1010.0011

3.a-a

a=-9 which means -a=9  so i have to do -9+9 and in binary:

10111+01001=100000...we discard 1 so result is 00000 which is 0 in decimal

b+c

(I added 4 bits after point cus fractional part must have 4 bits as it says)

0011.1100+1110.1100=10010.1000 we discard 1 so result is 0010.1000 and in decimal 2.5

c+a

01110.1100+10111.0000=100101.1100 we discard 1 so result is 00101.1100 but in decimal 00101 isn't -10 but 5 . I can't detect my mistake

I don't know if any of the above is right,so please correct me.Any help would be much appreciated!


texts:
A polynomial-time Turing machine algorithm is considered efficient if its run-time, in the worst-case, is bounded by a polynomial function in the input size. I'm aware of the strong Church-Turing thesis:

  Any reasonable model of computation can be efficiently simulated on Turing machines

However, I'm not aware of solid theory for analyzing the computational complexity of algorithms of $\lambda$-calculus.

Do we have a notion of computational efficiency for every known model of computation? Are there any models that are only useful for computability questions but useless for computational complexity questions?


texts: Applying a permutation on a sequence with multiplication

texts:
We are given a sequence of $n$ numbers called $\alpha$ and an arbitrary number $x$. Give an algorithm to find a permutation $\pi$ of size $n$ such that $\sum_{i=1}^n{\alpha_i.\pi_i} = x$ or tell if there is none.

Well I wasn't able to solve it in polynomial time and I'm not sure whether it's possible. So if it's NP would you give me some observations on the reason?


texts: A homework problem I have asks that I "state" a loop invariant, then "prove" it, then "apply" it. I get state and prove, but my textbook doesn't explicitly state how to "apply" a loop invariant.


texts: How do I decode a received polynomial code with an error?

texts:
As a message I get (5,0,1,3), which is coding a sequence of numbers of length 2 in $\mathbb{F}_7$ as polynom with the 4 support points a1 = 0, a2 = 1, a3 = 2, a4 = 6. In the transimission occured an error.
Calculate the original message.
How do I do this? In my script we didnt't talked about polynomial codes directly just about the cyclic code. And the topic of this exercise is polynomial codes.
Could someone please get me through this or explain a way? Thanks for any help!
Edit1:
Seems like I need a generator polynom? Right?
How do I get it? In my researching it seems like it's a fixed chosen one everywhere?


texts:
How it can possible

$\ 1/2n^2 -3n = Θ(n^2) $

Why we dont care $\ 3n $ and $\ 1/2 $


texts: Decidability of checking whether all words accepted by a TM have an even number of 1s

texts:
Let $\Sigma = \{0,1\}$, and consider the language
$$L = \{\langle M \rangle \mid
M \text{ is a TM and } L(M) \text{ is a subset of } Σ^* \text{ and all strings in this set have an even number of 1s}\}.$$

I think $L$ is undecidable. But I am stuck on proving it. I think it is equivalent to prove $L = \{\langle M \rangle \mid M \text{ is a TM and } L(M) \text{ is a specific set with an even number of 1s}\}$ is undecidable. How can I do some reduction for it?


texts:
The puzzle is made up of (n x n) squares so when taking the problem the input size would be n.

Rules of Masyu:

The goal is to draw a single continuous non-intersecting loop that properly passes through all circled cells. The loop must "enter" each cell it passes through from the center of one of its four sides and "exit" from a different side; all turns are therefore 90 degrees.
White circles must be travelled straight through, but the loop must turn in the previous and/or next cell in its path.
Black circles must be turned upon, but the loop must travel straight through the next and previous cells in its path.


texts:
I am trying to write a program in Python for the infamous egg drop puzzle using recursion. In case you do not know the problem statement, here it is:

https://code.google.com/codejam/contest/dashboard?c=32003#s=p2

One solution to this puzzle would be to use a recursive function that returns the maximum floors of a building that would be allow for $Solvable(F, D, B)$ to be true, represented as such, as function $f$:

$f(D, B)$ $=$ $1$ $+$ $f(D - 1, $ $B - 1)$ $+$ $f(D - 1$, $B)$

... where $D$ is the number of drops left, and $B$ is the number of breaks allowed. This solution makes use of how an egg can either break on $f(D - 1, $ $B - 1)$ floors below, and $f(D - 1$, $B)$ floors above.

As you can see, this results in the formation of a binary recursive function as shown above. Combined with the fact that we know that $f(1, B)$ $=$ $1$ for all values of $B$, and how $f(D, 1)$ $=$ $D$ for all values of $D$, this problem should be no problem to solve for a program that can handle recursion very well. However, Python has a knack for being unable to handle recursion as well as some other languages.

As such I would like to know whether the maximum floors returned by function $f$ can be determined for a set of values where $1<=D, B<=200,000,000$ in Python.

  Here is a list of the techniques I have tried so far, to little avail:
  1. Memoisation (Caching values of $f(D, B)$)
  2. Since we know that $f(d, b)$ for $d <= b$ is equal to $f(d, b)$ where $d = b$, with $d$ held constant, we can reduce the number of cached pairs of $d$ and $b$
  3. When $d = b$, $f(d, b)$ is equivalent to $2^d - 1$, thus removing the need for the binary recursion for $d = b$


texts: Assertion of Type Inference Rules/Type Checking

texts:
I have a problem in a book I am trying to accomplish.

I understand the overall type of the expression is boolean and how it derives. (y * x) will be rule 4 (counting from top right). (y * x) + x when evaluated will be rule 3 and the overall expression when evaluated will be rule 5.

What I want to figure out is what is the correct way to illustrate the my working? Can someone give or link an example of the correct way to answer a question like this?

Question 2

Proposed solution:


texts: Semi-decidability of the language $\overline{L_{\epsilon}}$

texts:
Firstly consider the problem: given $L_H = \{R(M)w : M \in TM_0, w\in L(M)\}$ where $R(M)$ are encoded transitions of $M \in TM_0$. Assume for contradiction $\overline{L_{H}}$ is semi-decidable, then there is $Q \in TM_0$ with $L(Q)  = \overline{L_{H}}$ therefore for every $M \in TM_0$ we have the following
$$Q \ accepts \ input \ R(M)w \iff M \ does \ not \ accept \ input \ w  \ \ \ \ (1)$$
Then we construct machine $Z$ s.t. doubles the input and runs machine $Q$. Observe the following for arbitrary $M \in TM_0$:
\begin{alignat*}{2}
Z  \ accepts \ input \ R(M) &\iff Q\ accepts \ input \ R(M)R(M)\\
&\iff M \ does \ not  \ accept \ input \ R(M)
\end{alignat*}
Taking $M = Z$ will yield us a contradiction. Hence, $\overline{L_{H}}$ is not semi-decidable.
The same technique I am trying to apply for the case $L_{\epsilon} = \{R(M) : M \in TM_0 \ \text{s.t. $M$ accepts $\epsilon$}\}$ where $R(M)$ are encoded transitions of $M \in TM_0$. But I am facing some troubles. Assume for contradiction $\overline{L_{\epsilon}}$ is semi-decidable, then there is $Q \in TM_0$ with $L(Q)  = \overline{L_{\epsilon}}$ therefore for every $M \in TM_0$ we have the following
$$Q \ accepts \ input \ R(M) \iff M \ does \ not \ accept \ input \ \epsilon$$
Then I cannot really find appropriate $Z$ for this case, as doubling the input simply won't work. Any suggestions are appreciated.


texts: Terminology: Difference between decision variables, features and attributes?

texts:
Could there be a difference between the words "feature", "attribute", and "decision variable" when used in the same paper? The one I am specifically thinking about is about an optimization method for clustering, but I am also wondering if there generally are any scenarios for which it could be.

I can't manage to google up an answer that either confirms or denies that these are the same thing, and I have no formal training in data science.

EDIT:

I left the article out at first to not omit a more general answer, but this is the link: ncbi.nlm.nih.gov/pmc/articles/PMC4532808

Some quotes:

"Mutation is a probabilistic operator that randomly modifies a decision variable of a candidate solution."
"Suppose [...] POPi(s) is the sth decision variable of POPi  (i.e.  C r t, t = 1,2,…, d  and  r = 1,2,…, q)."
"[...] max(h i(SIV)),  min(h i(SIV)) are the upper and lower bounds for each decision variable [...]"
"A SIV is a feature of the solution and can be imagined like a gene
in GA."


texts: Showing two Turing machines decide different languages

texts:
I want to figure out how two languages are different. If we have TM M and TM N, how would I figure out if the languages are different? My intuition is that if a M accepts an input a and N does not then that would prove the languages are different, right?

I'm not too sure if I'm thinking of this correctly.


texts: What strategy should I use to sovle this interview problem? May I apply DP on this?

texts:
The problem description is as below and it feels like a DP problem but I am not sure, thank you for helping!

You have a certain dose of a drug, say, 200 milliliters, and now some patients need this drug. The doses for each patient may vary from person to person, for example, 2.5 milliliters for A, B, C, 5 milliliters for D, E, and 7 milliliters for F, and so on. The question is, in short, how can you allocate the drugs so that you have the least amount of drugs left?
Example input: total drug dose 10 (milliliters).
A needs 3, B needs 5, C needs 2, D needs 4, E needs 2.
Output: A, B, C or A, B, E (perfect allocation with no drugs left).
Note: there may be decimals.

I appreciate any hints or solutions to this problem.


texts:
What is the definition of a 'simple path' in a finite acceptor?
My concern is whether self loops can be considered as a part of simple path from initial to final state?


texts: Church-Turing Thesis - the mechanical model - the turing machine- its limits and its equivalence with a modern digital computer

texts:
Well in many texts and places I have seen a called statement, which claims it self to the famous "Church Turing Thesis".
I have seen many texts say that based on Church-Turing Thesis :

"Anything that can be done by a digital computer can also be done by Turing Machine".

Peter Linz text roughly says that the thesis is :

"any computation that can be done by "mechanical" means can also be done by TM".

Linz even adds that mechanical term is not well defined. So TM can serve as a definition for mechanical machine.
A look in the Wikipedia says:

It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.

The Wikipedia indeed defines or considers Turing Machine to be that "mechanical" standard.
Googling about mechanical computation, results in the picture of a device something like this:
 Mechanical Computer
Even Ullman text has a proof of equivalence of TM and modern computer using the simulation of instruction set... But there the authors make a twist by saying they assume their digital computer says "yes" or "no" for input given.
Sipser says:

The definition came in the 1936 papers of Alonzo Church and Alan Turing. Church used a notational system called the λ-calculus to define algorithms. Turing did it with his “machines.” These two definitions were shown to be equivalent. This connection between the informal notion of algorithm and the precise definition has come to be called the Church–Turing thesis.

Most of the problems that can be solved by a TM in fact can be solved by applying the algorithm mechanically by an actual human using pen and paper. Like given a graph, one can trace out the TSP tour using pen and paper by drawing it and marking out the path. Or given two integers one can find the sum using pen and paper.
So in that case are our modern computers more powerful than a TM ? What is this mechanical model?
Using modern digital computers we can play Super Mario. Though Mario is after all a program and runs on the processor. The graphics rendering algorithms are algorithms after all. And some texts says that the notion of algorithm comes from the concept of Turing Machine. But a TM cannot possibly produce audio/video.
Then why some people believe that TM is equivalent to modern digital computers ? Or could we somehow use a multi dimensional TM and use each cell as a pixel to produce a picture.... I doubt?

I have seen the question here but it does not answer my query.


texts: Can an optimization algorithm be "universal"?

texts:
I am wondering if a Bayesian Optimization framework (e.g. Google's Vizier) can be used in lieu of a traditional solver like Gurobi or CPLEX.

In trying to answer this question, I realized that I don't know enough about optimization theory to answer a more general question: Just how interchangeable are heuristic approaches for solving computationally hard optimization problems?

Coming from an ML background, I'm reasoning by analogy with supervised learning problems: In ML, some methods like Neural Networks (with a sufficient number of layers) or Support Vector Machines are universal, in that they can approximate any shape decision boundary or regression function up to an arbitrary level of precision.

Are there equivalent algorithms in optimization theory that can be used to solve any optimization problem (linear, non-linear, continuous, discrete, etc...), e.g. can Genetic Algorithms or Particle Swarm Optimization be thrown at any optimization problem and give us a reasonable solution? SGD is used to solve NP-Complete problems (i.e. training a neural network) - does that mean that it can be used for any optimization problem?

I assume that the reverse is true: Not all optimization are universal, for example methods that work for LP or QP don't necessarily work for harder problems.

If it is indeed the case that some optimization algorithms are universal, is Bayesian Optimization one of these universal algorithms? Can be used to approach LP, QP, MIP, TSP, and NP-Hard problems in general?


texts:
I need help on this question:
Given a sorted array of distinct integers A[1, . . . , n], you want to find out whether there is an index i for which A[i] = i. Give a divide-and-conquer algorithm that runs in time O(log n).

How I can proceed?
Thanks a lot!


texts: What is 'K' in the Bounded Post Correspondence Problem?

texts:
I'm only just starting to learn about the PCP, and I'm especially interested in the Bounded version. From Wikipedia:

  One of the most important variants of PCP is the bounded Post
  correspondence problem, which asks if we can find a match using no
  more than k tiles, including repeated tiles.

I am not sure I understand what Wiki means by a 'tile' in this context.

I do understand that a typical PCP problem takes as input two equal-length lists of nonempty strings, each of which contains some number of words. An example is this:

M = (abb, aa, aaa) and N = (bba, aaa, aa)

In terms of the Bounded PCP, what would the integer K be here? Is it the length an individual word can be (which in this case is maxed at 3)? Is it the length of a single list?

Hope this is clear. I appreciate any help profusely in advance.


texts:
I'm running a q-learning agent in tic tac toe against a minimax agent and measuring the tie rate (since you can never win against minimax). When I run 10,000 training games, I've found that there seem to be two drastically different patterns:

1) Q-learning agent has a bad start and ends up with an overall tie rate of between 0.06 and 0.09.

2) Q-learning agent improves consistently and has an overall tie rate of around 0.7.

Why is this happening? Is the q-learning algorithm getting stuck in some local optima? Is this normal behavior for q-learning?


texts: (Un)Decidability of disjoint decidable and undecidable sets

texts:
I thought of this question today: given are a decidable set $A$ and undecidable set $B$ for which $A \cap B = \emptyset$. Is $A \cup B$ decidable or undecidable?

I am almost sure that it is undecidable but cannot come up with an argument/proof as to why, or even a counterexample.


texts: Is lambda calculus suitable for expressing semantics of non-functional languages?

texts:
Would it be convenient to express semantics of imperative languages (e.g. C) and object-oriented languages (e.g. Java) with $\lambda$-calculus?

Or in the other words: is $\lambda$-calculus a suitable candidate for expressing semantics of all context-sensitive languages?


texts: Eliminate non-local references from closure

texts:
For a code similarity detection framework I need to eliminate references to non-local variables, for example having the following closure:

{
  var a;
  var b;

  var f = function() {
    a = 5;
    b = 6;
  }

  f();
}

would be converted into something like:

{
  var a;
  var b;

  var f = function() {
    var a = 5;
    var b = 6;
    return tuple(a, b);
  }

  a, b = f();
}

Another approach would be:

{
  var world;
  var a;
  var b;

  var f = function(world) {
    world = update_world(world, "a", 5);
    world = update_world(world, "b", 6);
    return world;
  }

  world = f(world);
  a = get_world(world, "a");
  b = get_world(world, "b");
}

Basically, convert a stateful program to a purely functional one. The goal is then to transform the resulting program into the lambda calculus, normalize and look for isomorphic subtrees.

Is there a formalization of what I'm trying to do?


texts: If I have an MST, and I add any edge to create a cycle, will removing the heaviest edge from that cycle result in an MST?

texts:
Let's say that I have an MST, $T$. I pick an edge not in $T$ and change its weight, and add it to $T$ to create a cycle. Will removing the heaviest edge from that cycle result in an MST?

MST means minimum spanning tree of a graph. I came across these two posts:

https://stackoverflow.com/questions/13437702/how-to-get-the-new-mst-from-the-old-one-if-one-edge-in-the-graph-changes-its-wei
https://sudeepraja.github.io/MST/

and I follow both until the case where $w_{old}>w$ and $e\notin T$. They both say  that deleting the heaviest edge will guarantee an MST, but I don't see how to prove that. The cycle property just says that IF you have an MST, it can't have an edge which is the heaviest edge in a cycle of the original graph $G$; it is NOT saying that IF you have a tree that doesn't contain an edge that happens to be the heaviest edge of some cycle in the original graph $G$, you are an MST.

To make the question more explicit in terms of the problem it was trying to solve, I will copy a part of the first link:

  If its weight was reduced, add it to the original MST. This will create a cycle. Scan the cycle, looking for the heaviest edge (this could select the original edge again). Delete this edge.

I don't understand why this guarantees that we find an MST. Sure, we get a spanning tree but why does deleting this heaviest edge yield a MINIMUM spanning tree?


texts: Accounting method vs Potential method for analysing an augmented stack and differences with standard complexity analysis

texts:
With reference to chapter 17 of CLRS, (Amortized analysis). I'm trying to understand the differences between the accounting method and the potential method.

Let's start with standard analysis of the stack, three operations supported namely $\text{push}(x), \text{pop}(),\text{multipop}(k)$ the cost of this operations is respectively $O(1),O(1),O(\min(k,n))$, where in the latter $n$ is the size of the stack.

Standard complexity analysis of a sequence of operations $o_1,\ldots,o_n$ where for all $i$ $o_i \in \left\{ \text{push},\text{pop},\text{multipop}\right\}$ would lead to $O(n)$ as worst case. The reason of this is because whatever in the worst case the stack will have $n$ elements, and the worst case of $\text{multipop}$ will cost $O(n)$, hence we have the worst case. amortized cost will be $O(n)/n = O(1)$.

For the accounting method we will assign an amortized cost to each operation. If $o_1,\ldots,o_n$ are the operations above with costs $c_1,\ldots,c_n$ (real amortized cost) we assign amortized cost $\hat{c}_i$

$$
\hat{c}_i = \left\{
\begin{array}{ll}
2 & \text{if $o_i$ = push} \\
0 & \text{otherwise}
\end{array}
\right.
$$

Which means whenever we push an element $x$ in the stack we double it's cost due to the potential cal of $\text{pop}$ or the $i$-th iteration of $\text{multipop}$. Because of this we have the inequality

$$
T(n) = \sum_{i=1}^{n} c_i \leq \sum_{i=1}^{n} \hat{c}_i \leq 2n \Rightarrow T(n) = O(n).
$$

If we use the potential method instead we define $D_i$ the status of the data structure at iteration after executing $o_i$, and we define $\Phi(D_i)$ as the size of the stack after executing $o_i$.

By definition of the potential cost we will have

$$
\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})
$$

Three cases are distinguished

$$
\hat{c}_i = \left\{
\begin{array}{ll}
1 + (s + 1) - s & \text{if $o_i = \text{push}$} \\
1 + (s - 1) - s & \text{if $o_i = \text{pop}$} \\
k + (s - k) - s & \text{if $o_i = \text{multipop}$}
\end{array}
\right. =
\left\{
\begin{array}{ll}
2 & \text{if $o_i = \text{push}$} \\
0 & \text{if $o_i = \text{pop}$} \\
0 & \text{if $o_i = \text{multipop}$}
\end{array}
\right.
$$

Which is the same as the accounting method.
I can see a sort of relationship between the accounting and potential method, which in my mind is similar to the relationship between function and integral function, or function and derivative function. With this I mean, the in the accounting method we define a function $\hat{c}_i$ and we later compute a summation that bounds the actual worst case hopefully tighter than doing standard complexity analysis. In the potential method we instead define a function $\Phi$ that would allow to retrieve $\hat{c}_i$ using the finite difference, plus the actual cost. Is this correct? Is there also anything more subtle I'm still missing maybe? (some kind of clever observation regarding the two methods).

Also in both cases I still want to compute the actual cost per operation in order to perform the analysis. In the accounting method I need the summation to prove that the summation of the amortized costs bound the actual cost, in the potential method I need this cost per single operation. Computing the actual cost would be something I'd do normally in complexity analysis. Therefore the question is where is the actual advantage in using these two methods?


texts: Embedding high dimensional vectors into low dimensional space preserving similarity

texts:
I have a collection of high dimensional vectors such as $\vec{a}_{i} \in \mathbb{R}^{n}$ where $n$ is 3000. What I want to do is to embed these vectors into a space such as $\vec{b}_{i} \in [0, 255]^{n}$ where $n$ in this case is now 32. I want to embed it (using any hash trick or something like that) in a way that will preserve similarity. For example, if I have the following two vectors that are very similar to each other:

$\vec{a}_{1} = (1.2, 0.1, 0.4, 12.8, \ldots)$

$\vec{a}_{2} = (1.1, 0.1, 0.4, 12.5, \ldots)$

I want these two vectors to end in the same "bucket" of this other space where the vectors belongs to $[0, 255]^{32}$. Note that I don't want to use it for search, I want similar vectors to be in the same "bucket" in this other low dimensional space. I was trying to use LSH but I wasn't able to figure out a way to solve this.


texts: In Constraint Programming, are there any models that take into account the number of variable changes?

texts:
Consider a CSP model where changing the value of a particular variable is expensive. Is there any work where the objective function also considers the number of changes in the value of the variable during the search process?

An example: The expensive-to-change variable may be in the control of some other agent and there is some overhead of involving that agent to change the variable. Another example: The variable participates in one of the constraints, and the satisfaction of this constraint involves calling an expensive function (such as, a simulator), e.g. $z = f(x, y)$ is the constraint, and $f$ is an expensive-to-compute function. Therefore, $x$ and $y$ are expensive-to-change variables.


texts: find number in array divided into k parts

texts:
I was wondering what is the most efficient way to find the a number in an array with the following conditions:

  Array $A$ of size $n$ divided into even parts in the size of $k$

  every element in each part is bigger than all the elements in the part
  before (Lets say in the left)
  every element in each part is smaller then then every elements in the part after it (lets say on the right)

At this moment after trying couple of ways I am under the impression that the only way is $O(n)$

Is it correct?