texts: What is the name of the operator that translates from $X\rightarrow(Y\rightarrow Z)$ to $Y\rightarrow(X\rightarrow Z)$?

texts: Is there a standard name for the operator that takes a function $f:X\rightarrow(Y\rightarrow Z)$ and returns the function $f':Y\rightarrow(X\rightarrow Z)$ that satisfies, for every $y \in Y$ and $x \in X$, $f'(y)(x) = f(x)(y)$?


texts: Looking for algorithms with nested loops with unpredictable iteration counts

texts:
I am working on a compiler optimisation routine for GPUs that optimises nested loops which has unpredictable number of iterations. To test my routine I need some real-life algorithms that include this kind of loop construct.

For example, there is a queue A with an arbitrary number of elements of type a each of which contains some arbitrary number of elements of type b. The elements of A should be processed in sequential order. There is no way to know beforehand how many elements of type a should be processed (i.e. elements could be added to A during it's processing), or how many b elements the next a would contain.

Such is the case of literals/clauses queue in DPLL SAT solving algorithm (that was the initial reason for developing the optimisation).

Could someone name some other algorithms that include such nested loops construct?


texts:
" How long will it take for 2 jobs to complete if they're running in parallel, knowing that both have a total of 20 minutes of CPU usage time and 50% IO"

I calculated the CPU usage: 1-0.5²=75%.
To my understanding, if they're running sequentially, time needed to completion is 80 minutes (each job needs 40 minutes to complete)
therefore time needed to complete both jobs in parallel is 75% * 80 = 60 minutes.

However here is the correct answer:

" CPU utilization is 75%. Thus each one gets 0.375 CPU minute per real time minute. To accumulate 20 minutes of CPU time, a job must run 20/0.375=53.33 minutes. Thus, in parallel, time to completion for both jobs is 53.33 minutes".

I don't get where the 0.375 came from ?

What are CPU minutes ?

Help is appreciated


texts: Could a large quantity of coded information (let's say 10,000 GB) be copied from one storage device to another without first being decoded? If so, how long would something like that take?


texts: Proof of expected number of probes in an unsuccessful search (open addressing hashing)

texts:
I'm seeking some clarification on the proof of the expected number of probes in an unsuccessful search in open addressing hashing. The proof is given in CLRS on page 275, section 11.4 (Open addressing).

Specifically, why is the higher bound of an expectation (of unsuccessful probes) in search is $\infty$? What is the rational behind this?

$E[X] = \sum_{i=1}^{\infty} Pr\{X \geq i \}$ $(1)$ p. 275 CLRS

My understanding is that the maximum possible amount of probes in the worst case scenario is $n$. So, the expectation in this case is

$E[X] = \sum_{i=1}^{n} Pr\{X \geq i \}$ $(2)$

where n is the number of elements in a table of size m.

Of course, we can assume that $n \rightarrow \infty$, then $(1)$ makes sense. However, open addressing hashing is not recommended for large data sets. So, these two concepts contradict each other.


texts: Can a Language be determined by its kleene closure?

texts:
Lets assume that we have access to a oracle (machine that determines without details) for $L^*$, can we calculate $L$ from this machine?
The cost of operation is measured by number of queries from oracle.

Can any property of $L$ like being prefix free or regular help?

What if the language be finite and instead of $L^*$ we have an oracle access to $L^k$ for a known $k$?


texts: If a graph has a Euler cycle, do the biconnected components have Euler cycles as well?


texts: Why do we use RSA if it is not secure against chosen ciphertext attack?

texts: I am reading RSA cryptosystem from Farouzan book on network security. The author has mentioned that RSA encryption is prone to chosen ciphertext attack. Then why is this algorithm still so popular?


texts:
I have a question about the logic circuit performing the division ( http://userpages.umbc.edu/~squire/cs313_l20.html ).

I implemented it to some software but does not work.

I drew the schematic circuit blocks of four CAS (2x2). Drawn circuit implements the division number of 3-bits by the number of 2-bits.

I'm interested only remainder.

The problem is that eg. for divident equal to 1 (binary 001) and the divisor equal to 2 (binary 10) getting the remainder equal to 3 (binary 11).

I attached a schemat of such a system with the selected values of all inputs and outputs obtained for blocks CAS.

I do not know where it can be a mistake, because there are elementary operations (XOR, FADD, NOT).

Can you hint where I was wrong?


texts: Heterogenous and Asymmetric Computing's differences

texts:
The definition of the both architecture looks pretty same. They are parallel computing architecture with different type of cores.

What distinguish their definition, actually?


texts:
Imagine you are given a word samw and it is an invalid word (for the word same), and you need to find the correct word from the dictionary. The dictionary contains a list of words ordered by the frequency of the occurrence of the word with the most frequent word in the beginning.

There are the following rules on how to get the solution:

The wrong character should be adjacent to the correct character on the qwerty keyboard. In this case, w is adjacent to e.
You are given a method to get the list of adjacent characters of the keyboard

List<Character> getAdjacent(Character char)

You are also given method to find out if two characters are adjacent

boolean isAdjacent(Character a, Character b)

The wrong character can appear anywhere in the string and can be any number of characters also.
If there is more than one character matched for the wrong character, then return the string which is most frequent.

public String autoCorrect(String wrongWord, List<String> dictionary){

Question:  What is an efficient way to do this?


texts:
i am looking for an algorithm that will generate all possible combinations of words from given dictionary that satisfy given format.

Let me explain what i mean with format:

For example, if the format is "abcd" means that we are looking for one word, length of the word must be 4 and because all the letters in format are different, all the letters in the word must be different.

The format "computer science" means:

1) We are looking for 2 words (one of length len("computer") = 8 and one of lenght len("science") = 7)

2) The first char of the first word must be the same as the second char and the sixth char in the second word
   (letter "c" in format)

3) The seventh char of the first word must be the same as the the forth and the last char in the second word (letter "e" in format)

Is it better to generate all the possible strings in given format and the look them up in the dictionary or somehow build strings using dictionary ?

edit:

My idea:

1) split big dictionary (100 millions of words) into smaller ones based on word length.

2) for first word get trough all the entries in particular dictionary and try to match first word, then continue with the next one, but with more restrictions.

Thank you for your help!


texts: Recommendations for a good (rigorous) text to study Computational Complexity.

texts:
I look for a good text to learn basics of computational complexity.

I've read some parts of the first two chapters of "Computational Complexity: A Modern Approach" by Boaz Barak and Sanjeev Arora, it's readable and gives the big picture but I find it  not to be rigorious enough for me. I'm a mathematics student so I want a more rigorous treatment of the subject. So, the text I look for should:-

1- Define Turing machines formally and prove the basic results in a formal way not using  handy-waving arguments. For example, Boaz treatment of Turing machines is not rigorous and so I'd love to see more precise treatment of that.

2- Give proofs that are rigorous enough like those I read in mathematics texts and are not just "overviews".

What are your recommendations? What is the texts that satisfies my needs as close as possible?


texts: IF satisfiability problem belonged to P, can the certificate be found efficiently?

texts: IF SAT(satisfiability problem) belongs to P, then is it possible for a certificate of an arbitrary instance of SAT to be found efficiently?


texts:
I am having some difficulties splaying the element 4 to the root.
Considering the following splay tree.

0
 \
  1
   \
    2
     \
      3
       \
        4

Could anyone show me the steps how to get the 4 to the root?


texts: Upper and lower tangent line to convex hull from a point

texts: Is it possible to find an upper and lower tangent line to a convex hull in $log(n)$ time where $n$ is number of points on a convex hull? I have just done it in linear time where I checked for upper tangent line if orientation of $S,i,i+1$ is greater than zero (anti-clockwise) and if orientation of $S,i,i-1$ is greater than zero as well. Same for lower tangent line where I checked if its clockwise orientation. $S$ is a point from where I want my tangent line to go, $i$ is a point on a convex hull and $i-1$,$i+1$ are its neighbours. This is the only source I've found so far [Link]$_1$ and I really can't understand the algorithm for now.


texts:
Given a list of real numbers $p_1, \dots, p_n$, I am looking for a most efficient algorithm to sort this list in a "probabilistic ascending order", meaning that $p_i < p_j$ implies that it is likely for $i$ to be placed before $j$, but not certain. In principle, every permutation is a possible output, but the less sorted the permutation is, the less likely it is to occur.

The best solution I could come up with is to modify selection sort. Instead of selecting the minimal element in every step, you select a random element with probability proportional to $\frac{1}{p_i}$. This has quadratic complexity of course, so I was wondering if there are better alternatives.


texts: Find number of candidate keys given non-trivial functional dependency X->Y, where X is some set of attributes and Y is some prime attribute

texts:
In a relation R, if X is some set of attributes and Y is some prime attribute such that X uniquely determines Y is a non-trivial FD. Then is it true that R has at least two candidate keys?

For instance, take the relation schema R(Class_Id, Course_Number, Instructor_Name, Text). {Class_Id, Course_number} is a candidate key. This makes Course_Number a prime attribute.
The following functional dependency holds on R:

{Instructor_Name, Text} uniquely determines {Course_Number}

How to determine if another candidate key exist or not?

EDIT: A Relational table
Class_Id | Course_Number | Instructor_Name | Text

    2             b            Jodi           E
    3             c            Jack           N
    2             c            Jack           N
    4             b            Peny           E
    5             e            Jodi           N


texts: Solutions to Diophantine Equations using a Min Heap

texts:
I've recently come across this problem:

  Find all solutions to the equation $a + 2b^2 = 3c^3 + 4d^4$ for which $a, b, c, d$ are all less than $100,000$.
  Hint: use one min-heap and one max-heap.

I can think of an algorithm involving two min-heaps (one for the LHS and one for the RHS), but can't figure out how a max-heap can be used. It needs to be efficient.

How could a max-heap be incorporated?


texts: How can Kolmogorov complexity help me practically with measuring entropy?

texts:
A comment was made to me saying the following in relation to Kolmogorov complexity:-

You're not the first to think non-computability = impractical or even useless. But it can be useful. In particular to random, "non-algorithmic" data.

I now have a physical   box on my bench that outputs perfectly random bytes with the following distribution:-

I'm trying to estimate the entropy rate of this box, and the problem is that these bytes are highly correlated. Very highly. I can't stress that enough. They are not independent nor identically distributed and arrive in blocks of 20,000ish bytes but that length varies randomly too.
How can Mr. Kolmogorov be useful to me with measuring this "non-algorithmic" data?

How to practically measure entropy of a file? has not yielded a practical answer so far.


texts: $O(n^2)$ running time vs $O(n^2)$ worst case

texts:
The use of the phrase "worst-case running time" is really confusing to me.
Isn't plainly stating that the time complexity of an algorithm is $O(n^2)$ supposed to mean that the growth rate of the algorithm is sub-quadratic?
If it is then why do we say that $O(n^2)$ is the worst case time?
Or do they have different meanings?
Thank you.


texts: Test whether two languages are equal, when give in algebraic form

texts:
This sub-problem is motivated by Algorithm to test whether a language is regular.

Suppose we have two languages $L_1,L_2$ that are expressed in "algebraic" form, as formalized below.  I want to determine whether $L_1 = L_2$.

Is this decidable?  If yes, can anyone suggest an algorithm for this?  If not, can anyone suggest a semi-algorithm (one that returns "equal", "not equal", or "I'm not sure"; where we want it to return "not sure" as rarely as possible).

Motivation: A solution to this sub-problem would be helpful for solving Algorithm to test whether a language is regular

Algebraic form. Here's one possible definition of what I mean by a representation of a language in algebraic form.  Such a language is given by

$$L = \{E : S\}$$

where $E$ is a word-expression and $S$ is a system of linear inequalities over the length-variables, with the following definitions:

Each of $x,y,z,\dots$ is a word-expression.  (These represent variables that can take on any word in $\Sigma^*$.)
Each of $x^r,y^r,z^r,\dots$ is a word-expression.  (Here $x^r$ represents the reverse of the string $x$.)
Each of $a,b,c,\dots$ is a word-expression.  (Implicitly, $\Sigma=\{a,b,c,\dots\}$, so $a,b,c,\dots$ represent a single symbol in the underlying alphabet.)
Each of $a^\eta,b^\eta,c^\eta,\dots$ is a word-expression, if $\eta$ is a length-variable.
The concatenation of word-expressions is a word-expression.
Each of $m,n,p,q,\dots$ is a length-variable.  (These represent variables that can take on any natural number.)
Each of $|x|,|y|,|z|,\dots$ is a length-variable.  (These represent the length of a corresponding word.)

My goal is something rich enough to capture many of the examples we see in textbook exercises.  (Feel free to suggest modifications to this formalization if it makes the equality-testing problem easier while still remaining expressive enough to capture many of the examples we see in textbooks.)

Some easier cases. If the original problem is too hard, here are some sub-cases that would still be interesting:

If $L_1,L_2$ are two languages specified in "algebraic" form as above, and $L_1\ne L_2$, let $d(L_1,L_2)$ denote the length of the shortest word that is an element of one of $L_1,L_2$ but not the other.  Can we upper-bound $d(L_1,L_2)$ as a function of the length of the descriptions of $L_1,L_2$?  Is it guaranteed to always be polynomial? at most singly-exponential?

Motivation: If we could prove it is always polynomial, this might help us exhibit a witness that $L_1 \ne L_2$.
If we omit the reversal operation (we do not allow $x^r,y^r,\dots$), does the problem become easier?


texts: Question about ε-moves at $\varepsilon NFA$

texts:
We learning know about ε-moves at $\varepsilon NFA$ and I'm little bit confuse...

If we have, for example, this  $\varepsilon NFA$:

and we have the word "$a$" - can we end the run at $s$? Or the running will be finish at $q$?
In other words what I'm tring to ask is this:
When we have an $\varepsilon$ - we first of all reading the letter from the input and then "jump"? or we can "jump" and then reading the input? (or we can do both).

I look at the definition of: $\hat{\delta}(q,a)$ (for a word) and $\delta(q,a)$ (for a letter), and I'm not sure if the answer to my question dependence at $\hat{\delta}(q,a)$ or $\delta(q,a)$, because:
$\hat{\delta}(q,a)=\{q,s\}$ and $\delta(q,a)=\{q\}$.

Thank you so much!
I hope I was clear (because I'm little bit confuse...)


texts: Clarification of Definition for Functional version of TSP

texts:
The decision version of $TSP$ is $NPComplete$. I was reading about the functional version of $TSP$ i.e. the class $FP^{SAT}$.

It is mentioned in the original paper that TSP is complete for the class $FP^{SAT}[n^{O(1)}]$. By definition of the class, it means TSP can be solved in polynomial time by making $[..]$ calls to an $NP$ Oracle.

But I am still confused what $n$ is in case of a TSP instance?


texts:
I know in Agda, rewrite is a syntax sugar that desugars to a with abstraction.
For example, if we have (I'm using the Data.Vec from the standard library):

$$
\DeclareMathOperator{Set}{Set}
\DeclareMathOperator{xs}{xs}
\DeclareMathOperator{where}{where}
\DeclareMathOperator{proof}{proof}
\DeclareMathOperator{data}{data}
\DeclareMathOperator{rev}{rev}
\DeclareMathOperator{ff}{ff}
\DeclareMathOperator{lemma}{lemma}
\DeclareMathOperator{intro}{intro}
\DeclareMathOperator{id}{id}
\DeclareMathOperator{refl}{refl}
\DeclareMathOperator{params}{params}
\DeclareMathOperator{Vec}{Vec}
\DeclareMathOperator{rewrite}{rewrite}
\DeclareMathOperator{with}{with}
\DeclareMathOperator{revrevid}{revrevid}
\begin{align*}
& \revrevid : \forall \{n \ m\} \{A : \Set n\}
    (a : A) (v : \Vec A \ m) \rightarrow
    \rev (v \ {:}{:} ^r a) \equiv a \ {:}{:}\rev v \\
& \revrevid \ \_ \ [] = \refl \\
& \revrevid \ a \ (\_ \ {:}{:} \ \xs) \ \rewrite \revrevid \ a \ \xs  = \refl
\end{align*}
$$

This will be desugared to:

$$
\begin{align*}
& \revrevid : \forall \{n \ m\} \{A : \Set n\}
    (a : A) (v : \Vec A \ m) \rightarrow
    \rev (v \ {:}{:} ^r a) \equiv a \ {:}{:}\rev v \\
& \revrevid \ \_ \ [] = \refl \\
& \revrevid \ a \ (\_ \ {:}{:} \ \xs) \with \ \rev (\xs \ {:}{:}^r \ a) \ | \ \revrevid \ a \ \xs \\
& ...  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | \ {.}(a \ {:}{:} \rev \xs) \ | \refl = \refl
\end{align*}
$$

But in Idris, there's nothing like a with abstraction, or a dot pattern (which are available in Agda).
So how does Idris' rewrite implemented? Is that just a syntax sugar or a language feature which cannot be implemented in pure Idris code?


texts: Approximation algorithms for an instance of the Monotone circuit satisfiability

texts:
I have the following problem. Given a below boolean formula (of the type explained below) containing $n$ literals and two parameter $k$ and $l$, come up with a satisfying assignment of literals such that no more than $k$ of them are set to true. ($l$ will be explained below.)
An example boolean formula with 4 literals is as follows: $ (x_1 \lor (x_2 \land x_4)) \land (x_2 \lor (x_3 \land x_1)) \land (x_3 \lor (x_4 \land x_1)) \land (x_4 \lor (x_3 \land x_2)) $. Some properties of the kind of formulae I am dealing with:

The number of outermost clauses (connected via AND) is same as the number of literals.
There is a restriction on size of the innermost AND clauses, they can have at most $l$ literals. For example $l=2$ in the example above.

I did some literature search to realize that this is called as the "Monotone circuit satisfiability" problem in the complexity parameterization literature. My interest in the problem is largely practical, so I am looking for the best approximation algorithm known for the above problem. Any help / suggestions are much appreciated.


texts:
Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a flag and either one element plus a pointer or two pointers. All dictionary and free-list operations should run in O(1) expected time. Does the free list need to be doubly linked, or does a singly linked free list suffice?

Please tell me if my understanding is correct: each slot in T[0,1,2….m-1] is storing (1) a flag (2) an element (3) 2 pointers
So, instead of the slot T(h(k)) being a pointer to a list, it is able to save one element and then that element points to a list
There is also a “free list”
There is only one flag for each slot T[0,1,2….m-1]
To insert an element ‘x’ we will first check T[h(x.key)] to see if it is free. If it is free then we insert T[h(x.key)] and change the flag = 1
If it was not free, then there is a list, so we insert it at the beginning of the list
To delete we will check x.prev and x.next to see if they are NULL. So when we delete the element ‘x’ we will be left with an empty list at that slot. So we insert T[h(x.key)] into the free list and update the flag to 0 and then delete the element x from the list its stores in
What I don’t understand is the functionality of maintaining a free list?  Is there a single free list for the whole hash table or does each slot have its own free list?  Also why insert the element to be deleted into the free list and then delete it? Why don’t just delete it without using the intermediate free list?
I am unable to visualize the use of the free list as mentioned in the question.


texts: Proof that POSITIVE-3-SAT is in the complexity class P

texts:
I have the following language:

$$\text{POSITIVE-3-SAT} = \{\langle\phi\rangle \mid \phi\text{ is a satisfiable boolean formula in conjunctive normal form,}\\ \text{ in which all clauses consist of exactly 3 literals and in which no variable appears negated}\}.$$

Progress so far:

My concern is that I have not understood the task. I have proposed what I think is a (near trivial) proof.

To show that the language is in P, my approach is to provide a deterministic algorithm which can decide the problem in polynomial time.

By definition, $\text{POSITIVE-3-SAT}$ must comprise of an arbitrarily long number of conjunctions of clauses of the form $(\lambda_1 \lor \lambda_2 \lor \lambda_3)$. Each clause is trivially satisfiable in the case that a truth value of TRUE is assigned to any of the clauses $\lambda_1, \lambda_2, \lambda_3$. On this basis, each clause containing 3 literals can be decided in $O(3)$ steps, $\equiv O(1)$.

If we make the assumption that the language is constrained to only contain a finite number of $n$ clauses, then we can say that the satisfiability of the language can be decided in $O(n) \equiv O(n^1)$ steps.

Thus, $\text{POSITIVE-3-SAT}$ can be decided by a deterministic algorithm in polynomial time.

Thus, $\text{POSITIVE-3-SAT} \in$ NP.


texts: Algorithm to compute sum of cost of all path between pair of unique vertices of a tree

texts:
Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of cost of all path between pair of unique vertices.

Thus, there are total nC2 or n(n-1)/2 such pairs. The time complexity of the mentioned algorithm is n(n-1)/2. Please suggest an algorithm with better space and time complexity if possible. Below is the pseudocode.

//Final Result
sumAllPair = 0;

//Total Number of vertices
N

//Adjacency List
adjacencyList: array of linked list

//Weighted Graph Matrix
weightedGraph: two dimensional integer array N*N

//Initialize Matrix
loop ii from 0 to N-1 {
    loop jj from 0 to N-1 {
        if(ii equals jj) {
            weightedGraph[ii][jj] = 0
        }else {
            weightedGraph[ii][jj] = INFINITY
        }
    }
}

currentVertex = 0
visitedSet: LinkedHashSet of Size N
lastVisitedVertex = -1
call allVertexPairSum(weightedGraph, adjacencyList, currentVertex, visitedSet, lastVisitedVertex)

print sumAllPair

/*
 * Say graph has vertices 1,2,3,4,5,6,7
 *
 * allVertexPairSum() will compute sum of cost of all path between pair of unique vertices like this:
 *              21 + (31+32) + (41+42+43) + (51+52+53+54) + (61+62+63+64+65)+(71+72+73+74+75+76)
 *              where ij represents cost of path from vertex i to vertex j
 *
 * Time Complexity:
 *      N(N-1)/2 or Combination(N,2)
 */
function allVertexPairSum(weightedGraph, adjacencyList, currentVertex, visitedSet, lastVisitedVertex) {

    for each  visitedVer in visitedSet{
        cost = weightedGraph[visitedVer][lastVisitedVertex] +  weightedGraph[lastVisitedVertex][currentVertex]
        sumAllPair = sumAllPair + cost
        weightedGraph[visitedVer][currentVertex] = cost
        weightedGraph[currentVertex][visitedVer] = cost
    }

    add currentVertex to visitedSet

    for each neighbourVert in adjacencyList[currentVertex] {
        if(neighbourVert not equals lastVisitedVertex) {
            //neighbourVert becomes currentVertex
            //currentVertex becomes lastVisitedVertex
            call allVertexPairSum(weightedGraph, adjacencyList, neighbourVert, visitedSet, currentVertex)
        }
    }
}

Here is an example:


texts: Scala as a language for Generic Programming

texts:
I posted the same Q at programmers.SE, but nobody really helps.

In the paper “An Extended Comparative Study of Language Support for Generic Programming” by Garcia et al. an interesting comparison of programming languages features for generic programming is given:

with the brief explanation of terminology:

Can anyone assess Scala programming language support for generic programming in a view of this framework? I.e. add a column in the first table with explanations and examples if possible.


texts: Infinite non-regular decompositions of regular languages

texts:
The title pretty much says it: I'm interested in examples of infinite families of non-regular, pairwise disjoint languages whose union is regular.
When is this the case?

Or, from a different perspective:
Given some regular language $L$, I want to find a family languages $(L_i)_{i \in \mathbb{N}}$ such that

$L_i \cap L_j = \emptyset$ whenever $i \neq j$
$\bigcup_{i \in \mathbb{N}} L_i = L$
$\forall i \in \mathbb{N}: L_i \notin \mathsf{REG}$

More specifically: When is such a decomposition possible (clearly, not every regular language is decomposable in this way, e.g. finite languages)?

A class of (motivating) examples is the following: Given some congruence relation $\sim$ on $\Sigma^\ast$ such that the elements of $\Sigma^\ast /\sim$ are non-regular, every language saturated by $\sim$ admits a decomposition as above. One such congruence is the congruence $\sim_R$ generated by the identities $\{a^2 \sim_R \lambda ~:~ a \in \Sigma\}$, assuming $|\Sigma| > 1$. An example for a language saturated by $\sim_R$ is the language consisting of words containing an even (odd) number of occurrences of some symbol from $\Sigma$. More generally, languages accepted by complete deterministic automata with symmetric transition relations (that is, $q\cdot aa = q$ for all states $q$ and symbols $a$) are saturated by $\sim_R$.

However, I fail to see some general criterion for a language being decomposable in this way.


texts: Why is the class NP-Complete important compared to NP-hard?

texts:
I'm studying computational complexity and I was wondering why the NP-Complete (NPC) problems is an important class at all. I find it obvious why we're interested in showing a given NP problem is NP-hard.

I also understand the definition of NPC, and that showing a given decision problem is NP-hard, knowing it is in NP, is exactly was NPC means.

However, what I don't understand is: why this concept is so important? Surely, if we find any NP-hard algorithm which runs in time P (whether or not that is in NP), we have shown that $NP = P$.

Why is this concept so important?


texts: About the complexity of deciding whether no two elements of a collection are the same

texts:
Given a collection of $n$ numbers, $S$, the question is to decide whether all the elements of $S$ are distinct from each other. If they are distinct from each other (no two of them are the same), print "Yes". Otherwise print "No".

I know the worst case time complexity of this question is $\Theta \left ( n\log n \right )$. Of course it is based on comparison among elements. But I can't figure out how to prove this. Perhaps using the decision tree?


texts: Theoretical worst case running time of finding a path through a maze?

texts:
Given a randomly generated maze of dimensions n x n, with the entrance point always being the top left corner (0,0) and the exit point always being the bottom right corner (n,n) what is the theoretical worst-case running time of finding a path through this maze?

The maze has a density of d (for example, if d = 0.5, then half of the maze is filled with obstacle/wall cells)
The path finding algorithm uses a stack to keep track of the path and for back tracking when necessary
The algorithm uses a search order of down, right, up, left


texts: In most locality sensitive hashing implemensions of SimHash, why is the cosine distance used and not the euclidean distance?

texts:
In Chapter 3 of Mining of Massive Datasets, the basis of locality sensitive hashing is explained. They notably mention simhash for the cosine distance, where random hyperplanes are generated, and for each hyperplane, the projection of the vector to be hashed onto the hyperplane's normal is used for hashing the vector. They highlight that to instead measure euclidean distance, one can involve the use of a value $a$ as a segment length, used to split all hyperplane normals into some number of $a$-length segments. For each hyperplane, the segment into which the vector's projection falls into is used as its hash output. Hence the concatenation of this operation on each hyperplane generates a hash.

Yet a number of implementations, including what seems to be one of the most authoritative (falconn), do not use segments at all, and instead simply do a binary output depending on which side of the hyperplane the projection falls into. Why is this ? Why are segments not used ? What does the cosine distance have over the euclidean distance ?


texts:
I was trying to find info about this Finite Automata type FAB (Finite Automata Bowl) and wasn't able to find a lot. It is basically the rules that apply to PDA apply to FAB except you drop the temporal order of the stack. So instead of being restricted to only removing the top symbol of the stack, you can remove any symbol of the bowl.

The question is, does there exist a context-free language that is not accepted by an FAB?


texts: language for Turing machine, {w#w | w ∈ {0,1}*}

texts:
Recently, I am studying a computation theory and got a question regarding turning machine.
let {w#w | w ∈ {0,1}*} be the language of a turning machine. it will accept, for example, 01#01.
however, if we have a turning machine accepting the language of {w#w | w ∈ {0,1}}. What string will it accept? is it going to be only 1#1 or 0#0 since * here is the representation of the closure?


texts:
Say I have $n$ vectors $\{ z_i \in \mathbb{R}^D\}_{i=1}^n$ (where $n$ is very large and hence I can't do any calculation which scales as $n$) and I want to create $n$ vectors $\{x_i \in \mathbb{R}^d \}_{i=1}^n$ with $d$ as small as possible, such that $\forall i,j <z_i,z_j>$ is either very close to $<x_i,x_j>$ OR w.h.p $  <z_i,z_j> = <x_i,x_j>$.

Is there a standard answer known for this - by maybe using hashing?
One possible way might be to either deterministically or randomly from some distribution pick some $D-d$ coordinates and drop those coordinates from each $x_i$ to get the corresponding $z_i$ such that for each pair on either side either the inner-product is well approximated or is equal with high-probability over the way the coordinates are sampled. Is such a way of sampling known?

For the second option one other way to think would be to pick an unit magnitude gaussian vector at random $g \in \mathbb{R}^d \subset \mathbb{R}^D$ and to define $x_i$ as the projection of $z_i$ along $g$. Then indeed one has that $\mathbb{E}_g[ <x_i,x_j>] = <z_i,z_j>$.

But can this above be shown to be true with high concentration or be derandomized?


texts: Can we count the number of times a particular state in a DFA is running in a loop?

texts: If in a particular DFA , we are looping in a state for n symbols.... Is there any way to keep track  of this 'n'?


texts: Calculating mean, min, max, sum of a list of integers - what's the complexity?

texts:
This is sort of a silly question that's been bugging me.

I have a list of 100k numbers that I am calculating some statistics for. Specifically, I am computing the mean, minimum, maximum, and sum of these numbers. I'm doing it using a fold. In JavaScript:

// define folding functions:
let mean = (a, b, index, array) => a + b / array.length
let max = (a, b) => Math.max(a, b)
let min = (a, b) => Math.min(a, b)
let sum = (a, b) => a + b

let fold = initial => f => data =>
  Math.round(data.reduce(f, initial))

// functions we can consume:
let averageDistance = fold(0)(mean)
let maxDistance = fold(-Infinity)(max)
let minDistance = fold(Infinity)(min)
let totalDistance = fold(0)(sum)

// compute stats:
let data = [1, 2, 3, ...]
let a = averageDistance(data)
let b = maxDistance(data)
let c = minDistance(data)
let d = totalDistance(data)

The time complexity of this is clearly O(n) for each statistic averageDistance, maxDistance, etc. Computed over all 4 statistics, the complexity is O(4n).

Now, I can instead compute all 4 statistics in a single loop, using either a transducer (a similar optimization to Haskell's fusion), or by inlining eveything into a for loop:

let a = 0
let b = -Infinity
let c = Infinity
let d = 0

for (let i = 0; i < data.length; i++) {
  a = mean(a, averageDistance(data[i]), i, data)
  b = max(b, maxDistance(data[i]))
  c = min(c, minDistance(data[i]))
  d = sum(d, totalDistance(data[i]))
}

This solution only does a single loop, so intuitively it does it in O(n) time (an improvement over 4n from before).

But it still does the same amount of work as before: (100k integers)*(4 statistics) = 400k computations.

Is one solution really faster than another? Is the difference in space complexity (not in time)? If no to both of these, why bother with transducers or fusion at all?


texts: Pushdown Automata for words x#y where x and y are different words over {0,1} that share one similarity

texts:
I was instructed to create a pushdown automaton described in the title. Basically, the pushdown automaton accepts strings of the form $x\#y$ where $x$ and $y$ are strings of 1s and 0s such that there must be at least one difference and at least one similarity between $x$ and $y$. Here is the meaning of one similarity. Let $x=x_1x_2\cdots x_m$ and $y=y_1y_2\cdots y_n$, where $x_1,x_2 \cdots, x_m, y_1,y_2, \cdots, y_n\in\{0,1\}$, then there exists an index $i$ such that $x_i=y_i$.

I understand that I must have two separate cases, with one case assuming that $|x| = |y|$ and one case where $|x| \not= |y|$. Right now I am only working on the case where $|x| = |y|$. So far, I am using nondeterminism to find the $i$-th value of $x$, matching it against the $i$-th value of $y$. However, this only determines if there is at least one difference between $x$ and $y$. I am failing to see a solution where I can also determine that there is at least one similarity. If anybody can point me in the right direction, it would be much appreciated.


texts: Defining a "repeat until"-construct in Denotational semantics

texts:
My Problem is: to define a "repeat until"-construct in terms of Denotational semantics. I made an attempt and now i need to know if i made it right.

The Conditions are: i used the language "While" as specified in "Semantics with Applications" by Nielson & Nielson (1992) (pdf) (WorldCat). I do not want to use the help of the While-construct.

In denotational semantics, we are interested in the effect of a program, rather than in "how" it is executed. Thats why semantic functions are defined compositionally. The corresponding definitions for the Denotational semantics (or "direct style semantics") can be found on page 86 in the Book from Nielson & Nielson (they made it avaible over the Internet).

My Approach is:
$$\mathcal{S}_{\text{ds}} \lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack = \text{FIX }F\\ \text{where }F\ g = \mathcal{S}_{\text{ds}}\lbrack\lbrack S\rbrack\rbrack\circ\text{cond}(\mathcal{B}\lbrack\lbrack b\rbrack\rbrack , \mathcal{S}_{\text{ds}}\lbrack\lbrack S\rbrack\rbrack\circ g, id)$$

As you might see, my approach is quite similar to the definition of while, but i cannot see a mistake in it.

post scriptum: Bounty given, and second edit: yes, i meant $$\mathcal{S}_{\text{ds}} \lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack$$ .. typo corrected.


texts: If all computations of non deterministic Turing machine on the input string are all accept then is the boolean formula of them a tautology?

texts:
If M is non deterministic Turing machine and w is any string then $\Phi_{M,w}$ is satisfiable if and only if M accepts w according to Cook and Levin (1971).

By the definition of non deterministic Turing machine, M accepts w if and only if M has an accept computation on w.

But if all computations of M on w are accept then is $\Phi_{M,w}$ necessarily a tautology more than just satisfiable?

We know for sure that if M rejects w then all computations of M on w are reject and $\Phi_{M,w}$ is unsatisfiable.


texts:
Not having received a satisfactory response to this question in math.SE, I am asking it here:

In this question, it is mentioned that the best known Boolean circuits for the Clique problem are non-monotone circuits that are smaller than monotone circuits for Clique. I’m looking for a reference to these best-known circuits. I would also welcome a sketch of how they work.


texts:
Having some trouble generalizing when a complexity class $D$ is closed under polynomial reduction.

For instance, take the following examples:

$\bigcup_{c \ge 1} \mathsf{DTime}(2^{cn^5})$
$\bigcup_{c \ge 1} \mathsf{DTime}(5^{cn})$
$\bigcup_{c \ge 1} \mathsf{DTime}(n^{c\log^5n})$

$P$ is contained in all of these classes, so if we are given a problem $A$  which belongs to one of those classes, and a reduction from another problem $B$ to $A$, the polynomial reduction won't affect the overall decision run-time. Can it be generalized to any class larger then $P$?


texts: How can, e.g., Dijkstra find all shortest paths in linear time?

texts:
As I understand one can modify BFS for unweighted graph or Dijakstra for weighted graph to find all possible shortest paths from $s$ to $t$ in linear time. But how can this be, when there are $O(2^n)$ such paths?
What am I missing here?


texts: How are Distributed Snapshot algorithms (likes of Chandy Lamport) implemented in real world distributed systems?

texts:
Can anyone explain, how Distributed Snapshot algorithms ( Example: Chandy-Lamport are implemented in the context of  modern distributed systems?

Can you name an open source System implementation which uses this / these class of algorithm?

How does this theory really translate to real world?


texts: Are you allowed to have empty states on Turing machine?

texts: So I'm doing some exercises with Turing machine and quite often it happens that a given set of states can be achieved if and only if some character was met. Therefore, we may have some states q3-q7 which the machine may be pointed to if and only if we spotted a and (because of the task spec, for example), we know that we may find only some chars (say b, d but not c, e) from the input language there so there's no need to have a separate state for every symbol. Can I then just program the states I'll actually use there and have some void states or do I have to put something there (like just reprinting the found character) anyway, even though I'm 100% sure the machine will never go to the state for some symbols?


texts: Given the same set of nodes, why is it (generally) easier to find a Euler cycle than a Hamilton cycle?

texts:
To find a Hamilton cycle is a NPC problem, but Euler is not.
Considering one can always transform the vertex as edge or vice versa conceptually. Then the vertex can be used to describe the information which originally edge does.

What properties make the Euler graph more easily to be resolved?

For example, in genome assembly problem, one can either consider a Kmer as vertex or edge(de bruijn graph), it's just two perspectives to look at the same thing. I think their should be additional or missing information between two kind of explanation.


texts:
Let $M_w$ be the DTM encoded by the binary string $w$ and let
$$L=\{w\#x\,|\,\text{all states are reached when running }M_w\text{ on }x\}.$$
I've already proved that this language is undecidable (the halting problem can be reduced to this), but is this language semi-decidable? I.e., is there an enumeration of $L$ or a reduction of $L $ to a semi-decidable language?


texts:
I am learning for my computability and complexity exam in which there is always an exercise to decide whether some problem is decidable or not.

In one of the past exams, there was the following problem:

Given Turing Machine M, decide whether there exists a prime number on which M halts.

I am supposed to decide whether the problem is decidable or not.

I guess I can rewrite the problem into the language $L = \{ \langle M \rangle | \exists p \in \mathbb{P} : M(p) \downarrow  \}$. I have been given a hint that I can use Rice's theorem to prove the language is undecidable. I am actually struggeling, since I have no idea how should I apply Rice's theorem to (generaly any) problem.

I am interested in these questions:

How can I find out whether Rice's theorem is applicable or not?
If I find it out, how to apply it? (In this excercise in particular)

Any help appreciated.


texts: Why is deep learning hyped despite bad VC dimension?

texts:
The Vapnik–Chervonenkis (VC)-dimension formula for neural networks ranges from $O(E)$ to $O(E^2)$, with $O(E^2V^2)$ in the worst case, where $E$ is the number of edges and $V$ is the number of nodes. The number of training samples needed to have a strong guarantee of generalization is linear with the VC-dimension.

This means that for a network with billions of edges, as in the case of successful deep learning models, the training dataset needs billions of training samples in the best case, to quadrillions in the worst case. The largest training sets currently have about a hundred billion samples.  Since there is not enough training data, it is unlikely deep learning models are generalizing. Instead, they are overfitting the training data.  This means the models will not perform well on data that is dissimilar to the training data, which is an undesirable property for machine learning.

Given the inability of deep learning to generalize, according to VC dimensional analysis, why are deep learning results so hyped? Merely having a high accuracy on some dataset does not mean much in itself. Is there something special about deep learning architectures that reduces the VC-dimension significantly?

If you do not think the VC-dimension analysis is relevant, please provide evidence/explanation that deep learning is generalizing and is not overfitting. I.e. does it have good recall AND precision, or just good recall? 100% recall is trivial to achieve, as is 100% precision. Getting both close to 100% is very difficult.

As a contrary example, here is evidence that deep learning is overfitting. An overfit model is easy to fool since it has incorporated deterministic/stochastic noise. See the following image for an example of overfitting.

Also, see lower ranked answers to this question to understand the problems with an overfit model despite good accuracy on test data.

Some have responded that regularization solves the problem of a large VC dimension.  See this question for further discussion.


texts: How to solve Tower of Hanoi iteratively?

texts: It may seem obvious to many but i am having a hard time figuring out the iterative solution to the Tower of Hanoi problem. There are some solutions on the Internet but without explanations. So can anybody give a sound explanation so that it becomes more intuitive and easy to reason.


texts: Cost to convert one integer array into another

texts:
This question is distilled from an interview question.
Given two arrays $a$ and $b$ containing $n$ integers each, change each integer in array $a$ into the corresponding integer in array $b$ by increasing or decreasing a single digit by $1$. What is the optimum algorithm?
The number of digits in $a[i]$ are the same as $b[i]$ and the length of arrays $a$ and $b$ are also the same.
An example, $a = [123, 456]$, $b= [124, 307]$. Then the minimum cost to convert array $a$ into array $b$ is 8.
I know of a naive solution to this question which of course is to count the number of increments to each digit but I'm wondering if there is a more efficient binary operation that can be used.


texts: Assumptions when selecting an algorithm or data structure

texts:
As I understand it the nature of data access (sequential or random) will determine the optimal algorithm/data structure to use when manipulating data.

What other assumptions need to be checked before selecting an algorithm or data structure for the manipulation of data?


texts: Is there an abstract architecture equivalent to Von Neumann's for Lambda expressions?

texts:
In other words, was a physical implementation modelling lambda calculus (so not built on top of a Von Neumann machine) ever devised? Even if just on paper?
If there was, what was it? Did we make use of its concepts somewhere practical (where it can be looked into and studied further)?

-- I'm aware of specialised LISP machines. They were equipped with certain hardware components that made them better but eventually they were still the same at their core.

If there isn't such thing, what stops it from being relevant or worth the effort? Is it just a silly thought to diverge so greatly from the current hardware and still manage to create a general-purpose computer?


texts: Limited sort: is this a well-known problem?

texts:
I came up with a problem, and I'm having trouble finding existing work on it. I'm not sure if there is a polynomial-time solution for it. Is this a well-known problem (or equivalent to one)?

We define a function limited_sort(input, n) -> output that takes an array of comparable elements input and an integer n and returns output which is a permutation of input such that that no element in output is more than n spaces from its original position in input. output is the permutation that has the lowest number of inversions (subsequent elements a, b such that a > b) out of all such permutations (if there are multiple minimal permutations, output is the lexicographically lowest of them).

For example, limited_sort([4, 1, 0, 2, 3], 2) returns [0, 1, 4, 2, 3], which has 1 inversion (4, 2). 0 inversions is not possible because you'd have to fully sort the list, and the element "4" would move 4 spaces which is not allowed. [4, 0, 1, 2, 3] is also valid with 1 inversion but it's lexicographically higher than [0, 1, 4, 2, 3].

Is there a solution that is polynomial-time in both n and L (the length of input)?


texts: Maximum Subarray Problem Algorithm that uses divide and conquer but runs in linear time

texts: I am trying to design an algorithm that computes the largest (by sum) contiguous subarray of an array of size n that uses a divide and conquer approach, but runs in linear time. The standard divide and conquer approach runs in O(nlogn) (can be found in chapter 4 of CLR) which is not what I am looking for. The following describes an O(n) divide and conquer algorithm: Page 16 https://software.intel.com/sites/default/files/m/d/4/1/d/8/10.1.1.150.7202.pdf however it goes over my head a little. Would anyone be able to shed some light on it?


texts: CLRS Exercise 24.3-4 - Confirm Output of a Program Claiming to Implement Dijkstra's Algorithm

texts:
I'm trying to better understand Question 24.3-4 From CLRS below:

  Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm.
  The program produces $v.d$ and $v.\pi$ for each vertex $v \in V$. Give an
  $O(V + E)$ algorithm to check the output of the professor’s program. It should
  determine whether the $d$ and $\pi$ attributes match those of some shortest-paths tree.
  You may assume that all edge weights are non-negative.

I have the answer from the Solutions manual, but simply do not understand how this answer actually works: (bottom of pg. 5/19, Exercise 24.3-4 didn't want to overload the question with a long solution):
https://sites.math.rutgers.edu/~ajl213/CLRS/Ch24.pdf

Basically, the solution says we have to check every edge $(u, v)$ for all $v \neq s$. I understand that we only need to ensure that $s.d = 0$ and $s.\pi = NIL$ since the $\delta(s, s) = 0$ and $s$ should not have a predecessor, as it is the first vertex in the graph. The solution goes on to mention that:

  "Check that $v.\pi$ is the vertex which minimizes $u.d +w(u, v)$ for all vertices $u$ for which there is an edge $(u, v)$, and that $v.d = v.π.d + w(v.π, v)$. If this is ever false, return false"

So I understand that for any $v \neq s$ that $v.\pi.d < v.d$ by the fact that $v.d = v.\pi.d + w(v.pi, v)$ so the distance of any node's predecessor must always be less than that of the node by the simple property.

How do we manage to check though that: "$v.\pi$ is the vertex which minimizes $u.d +w(u, v)$ for all vertices $u$ for which there is an edge $(u, v)$?"

Since say we pick some random vertex in the graph that is a neighbor of $s$, call this node $v$. So $\delta(s, v)$ could potentially be calculated by traversing half of the graph then coming back to $v$ through some other node, $u$ if the $w(s, v)$ is extremely large. How does the algorithm verify cases like this? Does it ensure that it starts only at the neighbors of $s$ first, verify those distances, and essentially inductively proceed to verify the remaining predecessors and distances?

It seems that for $v \in V - {s}$ that if $v.\pi$ is correct, then all that remains is to verify $v.d$? I just don't really understand how the algorithm can correctly do this.. Is it traversing the graph, or iterating over the adjacency list/set of edges for each node, such that for a node, $v$ we check all edges $(u, v)$ somehow and then come up with an understanding of whether the node $v$ has the proper $v.\pi$?

Could someone please help/explain how this solution works? Have been struggling for a few hours now on this, and stepped through the algorithm with written examples but am not seeing the pattern here. Thank you.

Edit I've seen some answers mentioning creating a tree (since Dijkstra's algorithm is supposed to output a shorted path tree from the src node, $s$).

Regarding this: Would we create a shortest path tree using all of the $v.\pi$ values for each $v \in V - \{s\}$, since $s.\pi = NIL$? This takes time $O(V + E)$ to create an adjacency list we would need to traverse using BFS/DFS. Then, we begin a DFS on the tree created by the $v.\pi$ attributes and modify the DFS to check $v.d = v.\pi.d + w(v.\pi.d + v)$ or something along these lines?


texts: Understanding Interval Schedulling problem requirement

texts:
Here is a modification of the weighted interval scheduling problem.

Given $n$ intervals by their end points $s_i$ and $t_i$ for $1 ≤ i ≤ n$, I want to minimize number of intervals so that every interval has a nonempty intersection with one of the selected intervals. In other words, select $S ⊆ {1,..., n}$ such that for each $1 ≤ j ≤ n$, interval $j$ intersects with some interval $i ∈ S$.
We say that the $j^{th}$ interval $[s_j, t_j]$ overlaps with $i^{th}$ interval $[s_i, t_i]$ if there exists a point $x$ such that $x$
belongs to the $i^{th}$ interval and the $j^{th}$ interval. A point $x$ belongs to an interval $[s, t]$ if $s ≤ x ≤ t$. Assume that $s_i
’s$ and $t_i's$ are distinct.

What I'm confused on is what this problem is even asking. It says minimize the number of intervals so that every interval has a non-empty intersection with a selected interval. So I get that means I want to find an interval that overlaps with another interval. But am I trying to find a sequence that avoids this as much as possible? In other words, am I just trying to set it up so that I maximize number of intervals while also minimizing overlapping intervals or am I trying to do something different?


texts: Speed up minimizing quadratic function by FFT

texts:
I'm trying to understand the following excerpt from a paper:

  Subproblem 1: computing $S$. The $S$ estimation subproblem corresponds to minimizing
  $$
\sum_{p}(S_p - I_p)^2 + \beta((\partial_xS_p - h_p)^2 + (\partial_yS_p - v_p)^2)  \tag {7}\label{7}
$$
  by omitting the terms not involving $S$ in Eq $(6)$. The function is quadratic and thus has a global minimum even by gradient descent. Alternatively, we diagonalize derivative operators after Fast Fourier Transform (FFT) for speedup. [Emphasis added] This yields the solution
  $$
S = \mathscr{F}^{-1} \left( \frac{\mathscr{F}(I) + \beta(\mathscr{F}(\partial_x)^*\mathscr{F}(h) + \beta(\mathscr{F}(\partial_y)^*\mathscr{F}(v))}{\mathscr{F}(1) + \beta(\mathscr{F}(\partial_x)^*\mathscr{F}(\partial_x) + \beta(\mathscr{F}(\partial_y)^*\mathscr{F}(\partial_y))} \right) \tag{8}\label{8}
$$
  where $\mathscr{F}$ is the FFT operator and $\mathscr{F}^*$ denotes the complex conjugate. $\mathscr{F}(1)$ is the Fourier transform of the delta function. The plus, multiplication, and division are all component-wise operators. Compared to minimizing Eq. $\eqref{7}$ directly in the image space, which involves very-large-matrix inversion, computation in the Fourier domain is much faster due to the simple component-wise division.

I don't understand how Eq.(8) was derived. How can FFT speed up gradient descent?

Cited by

"Image Smoothing via L0 Gradient Minimization"
Li Xu, Cewu Lu, Yi Xu, Jiaya Jia
ACM Transactions on Graphics, Vol. 30, No. 5 (SIGGRAPH Asia 2011), Dec 2011

pdf link in page 4


texts: Is there an NP-complete problem that can be solved in $O(n^{\log n})$ time?

texts:
I'm following an online course which has the following (multiple-choice) quiz question:

  Which of the following statements cannot be true, given the current
  state of knowledge?

  Some NP-complete problems are polynomial-time solvable, and some NP-complete problems are not polynomial-time solvable.
  There is an NP-complete problem that is polynomial-time solvable.
  There is an NP-complete problem that can be solved in $ O(n^{\log n}) $ time, where $ n $ is the size of the input.
  There is no NP-complete problem that can be solved in $ O(n^{\log n}) $ time, where $ n $ is the size of the input.

It seems to me that (1) and (2) are false since it has not been proven that any NP-complete problem is polynomial-time solvable. So I'm vacillating between (3) and (4).

In particular, I'm a bit nonplussed where the $O(n^{\log n})$ comes from; I haven't seen this expression in any of the lecture notes. However, I do know about the traveling salesman problem which can be solved in $O(n^2 2^n)$ time using the Held-Karp algorithm. It would seem to me like this function grows less faster asymptotically than $O(n^{\log n})$, since it is usually the expression in the exponent that matters the most, in which case the answer would be (3).

Is this correct? Also, how would I show this formally?


texts: What is the worst case for C++ "sort" function?

texts: So, what is the worst case for C++ "sort" function, when does it go to O(n^2) time? I know it's QuickSort, therefore, it's very fast in most cases, but it gets to O(n^2) in special cases. I've tried to figure it out via measurements, but I have trouble interpreting the results.


texts: Using vector clocks vs. directed acyclic graph for causality detection in distributed systems

texts:
I'm trying to understand how vector clocks compare to DAGs for causality detection in a distributed system.
When trying to detect causality relations in a distributed system, a very commonly proposed technique is the use vector clocks. Vector clocks are presented as:

Timestamping is a common method of totally ordering events in concurrent programs. However, for applications requiring access to the global state, a total ordering is inappropriate. This paper presents algorithms for timestamping events in both synchronous and asynchronous message-passing programs that allow for access to the partial ordering inherent in a parallel system. The algorithms do not change the communications graph or require a central timestamp issuing authority.

Source: Timestamps in Message-Passing Systems That Preserve the Partial Ordering Colin J. Fidge
Another less mentioned but nonetheless ubiquitous method is to synchronize a directed acyclic graph (DAG) between the replicas. I understand the "reachability" notion of DAGs allows to define a partial order between events. To my understanding, this is Git's approach to determining if a commit took place before, after, or at the same time as another.
I've seen little to no discussion opposing vector clocks to full DAG modeling. Unless I missed anything I think those are techniques that both could be used to do an event partial ordering in a distributed system. Trying to understand what unifies or separates vector clocks and DAGs, I've come to the following conclusion so far:
What unifies them:

They both could be used to determine causality relation in a distributed system

Advantages of vector clocks:

Size of data to synchronize in vector clock grows with the number of replica, but not with the number of events; which in most real life application is more efficient. Also optimizing DAG data transfer between replica over the network may not be straightforward.

Advantage of DAGs:

Easier to conceptualize? And possibly implement?
Models the full tree, so wins over vector clocks when we want not only to understand if an event e1 occurred before another event e2, but want to access more details on the event present, possibly their content, etc.
More expressive than vector clocks because vector clocks DAGs are constructed with a specific algorithm that constrains the expressiveness, and there are things you cannot do, such as taking three or more previous events to build one new event (at least from my understanding of the original paper, but that limitation may be challenged)

Is this it, or am I missing an important concept?


texts:
I was studying computer science and I learnt that Serial Data transmission is when one bit is transmitted at a time over one wire/channel. Then what does '8 bit serial' data transmission mean?
I was studying about MIDI where it said it uses 8 bit serial data transmission and is asynchronous.

Also, I cannot seem to find an appropriate tag to set to this question.


texts: Proof of QuickSort algorithm correctness

texts:
Recently I’ve studied QuickSort and understood its general idea.

Basically, we do the following:

Pick an element from the array (no matter which one and how in this context)
Rearrange elements in the array so that elements less than the pivot are placed prior to it (in the left part of the array), and ones that are greater than the pivot are placed after it (in the right part).
Apply these procedures to the left and right parts of the array.

Everything looks quite clear, but my question is: why does it eventually sorts the entire array?

I’ve read lots of articles about the QuickSort, but none of them provides a clear proof that algorithm does really work in a way they describe. So I’m looking for such a proof.

I realize that:

Array of one element (i.e with length 1) is already sorted.
After any partition the pivot is placed on it’s final position.

So what’s the proof of the fact that after applying QuickSort procedure to a given array of length N its elements will be ordered after a procedure completes?

P.S. I’ve seen several proofs based on mathematical induction. Unfortunately, I’m not familiar with it yet, so I’m primarily looking for non-induction proof.

Here they are:

https://www.cs.mcgill.ca/~dprecup/courses/IntroCS/Lectures/comp250-lecture17.pdf
Trying to understand this Quicksort Correctness proof
https://course.ccs.neu.edu/cs5010sp17/Efficiency/quicksort5.html


texts: Whether equivalence of different types of automata is of P-type?

texts:
I came across following problem:

  Which of the following problems is/are P-problems?
  (I) Equivalence of DFA's
  (II) Equivalence of NFA
  (III) Equivalence of regular expressions

Now I know I there exist neat algorithm to find whether given two DFAs are equivalent or not. So (I) must be P-problem. I am doubtful about (II) and (III). There is a procedure to convert every NFA to DFA. So to check whether equivalence of two NFAs, we can first covert them into DFAs and then check their equivalence in P-time. But seems that we cannot convert NFA to DFA in P-time, hence equivalence of NFA seems not a P-problem. Same for (III). Am I correct with this?


texts:
Let:
$ G = <V, \Sigma, R, S >: \\
V = \{ S,A,B,C \} \\
\Sigma = \{0, 1\} \\
R: \\
S \to CSC|A \\
A \to 0B1|1B0 \\
B \to CB|\epsilon\\
C \to 1|0
$

I need to find the language (no need to formally prove).
I have written many words but cannot seem to find a rule.
After trying that path I rewrote the grammar in a shorter rules:

$$
S \to 0S0|0S1|1S0|1S1|0B1|1B0 \\
B \to 1B|0B|\epsilon
$$

What should be my way of finding any pattern? to go each possible path independently ?


texts: how is the set of undecidable programs related to the set of non-halting programs?

texts:
Is there a non-halting program for every undecidable program? is undecidable the "same thing" as non-halting?

Thanks!


texts: A second question on "Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs"

texts:
Let B={M1,M2,...} be a Turing-recognizable language consisting of TM descriptions. Show that there is a decidable language C consisting of TM descriptions s.t. every machine in B has an equivalent machine in C and vice versa.

I saw a hint on solving this question which is given in the following picture:

But I have a difficulty in constructing such enumerator $E_{0}$, Also how will I show that every machine described in $B$ has an equivalent machine in $C$ and vice versa, could anyone help me in doing so?

Also it is worth to say that the solution of this problem is found here:

Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs

But I could not understand it. could anyone explain the solution for me in a simple way ? and in a way depending on the above hints?


texts: How to define a path between two sets of vertices?

texts:
In section 17.2 of the book "Combinatorial optimization polyhedra and efficiency" by Schrijver, he describes the Hungarian method for maximum weight matching in bi-partite graphs (with classes $U$ and $W$). He defines for a matching, $M$, $U_M$ and $W_M$ as the set of vertices in $U$ and $W$ missed by $M$. He then says "if there is a $U_M - W_M$ path, find the shortest such path". I'm not sure what this means. How is a path between two sets of vertices defined?
He is describing this path on a directed graph, $D_M$ where all edges in $M$ are directed from $U$ to $W$ and edges not in $M$ are directed from $W$ to $U$.


texts: Constructing logical sentences that involve negative integers over the nonnegative integers

texts:
Consider the following statement:

  If $x$ and $y$ are integers and $z$ is a nonnegative integer and $x + z = y$, then $x$ is at most $y$.

I'd like to build a sentence for this statement in the model of $(\mathbb{N}, +)$, where $\mathbb{N}$ is the set of nonnegative integers and $+$ is just the relation (where here I define a relation as a mapping from tuples to a boolean value): $\{(a,b,c): a + b = c\}$. By "sentence", I mean a logical formula with no free variables.

How can I write the highlighted statement in terms of the given model if variables in this model can only take only take on nonnegative integers? It seems at best I can only build a sentence in this model for the following statement:

  If $x$ and $y$ are nonnegative integers and $z$ is a nonnegative integer and $x + z = y$, then $x$ is at most $y$.

Or is it possible to define negative quantities in the model of $(\mathbb{N}, +)$?


texts: What is meant by a language have a "finite specification"?

texts:
I'm studying my notes for a formal language course and it them it states

  The vast majority of languages over a finite alphabet cannot be
  represented by a finite specification.

I don't understand this. What is meant by "specification"? It then goes on to show why this is true by showing some sets of the alphabet are countably infinite and others are uncountably infinite.


texts: Is the closure of P under e-free homomorphisms equal to NP?

texts:
The context free languages can be obtained as the closure of the Dyck language under the cone operations. The Dyck language $D_2$ is a deterministic context free language, and the cone operations correspond to the operations that can be implemented by nondeterministic finite state transducers. This result becomes less surprising, if we consider that nondeterministic finite state transducers can provide certificates (or verifiers, or witness strings, I wrongly called this oracle strings initially) of length $O(n)$, where $n$ is the length of the input string.

The definition of the class $\mathsf{NP}$ allows for certificates of length $O(n^c)$, but many $\mathsf{NP}$-complete problems are perfectly happy with certificates of length $O(n)$. The transducer should not change the length of the input uncontrollably, so we need faithful cone operations. For $\mathsf P$, this should be equivalent to closure under e-free homomorphisms. (Intuitively, the homomorphism removes the certificate). Hence my question:

  Is the closure of $\mathsf P$ under e-free homomorphisms equal to $\mathsf{NP}$?

As stated above, this question should be equivalent to the question whether certificates of length $O(n)$ (instead of $O(n^c)$) are enough for $\mathsf{NP}$.


texts: Generate a Grammar from a language(Non-CFL)

texts:
I tried to solve this question,

We have this Language, L(g)={AA|A={0+1}*}

The output(Productions) must be similar as these = {(11 11), (0 0), (1101 1101), etc..} The left side equal to right side..
VT={1,0}
The problem I used a lot of methods to solve this, like pumping lemma.

This question isn't easy, I hope someone could help.

a try: If we supposed that S->ASD|BSC|E, A->0, B->1, C->0, D->1
E : Empty
S->BSC->BBSCC->BBADCC let's convert from non-treminal to treminal .. BBADCC->>110100  so this Grammar isn't accepted..

How do I make sure left side = right side>

Make sure This isn't duplicated question.


texts: Is every planar graph a possible dual graph of a voronoi diagram?

texts: My question is: Given a planar graph defined by its adjacency matrix. Can I always find a set of points, so that the dual graph of the voronoi diagram of that set of points is the same as the planar graph?


texts: Build a regular grammar for a regular language

texts:
The language considered is the infinite set of all chains that meet the following conditions.

Conditions:

1) They consist of symbols from the set {1,a,b}.
2) They always start with the subchain '1a'.
3) They always include at least one subchain 'aa'.

For example:

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

One regular expression for this language seems to be like this: $1a ((1+b)^* a)^* (a (1+b)^* )^* a (1+b+a)^*$

How to find a regular grammar for this language?

I've thought of many ways but it seems to be too complex for me. I tried the following as solution, but it is not correct, I guess.

G ({1,a,b}, {A,S}, P, S)
P:
S -> 1S|bS|aA
A -> 1A|bA|1a


texts: Given an array with N elements and an array of N indices find the lowest possible amounts of swaps

texts:
So I have two arrays $d$ and $s$ with size $n \in \mathbb{N}$. Array $d$ contains the elements and array $s$ contains indices. Array $s$ contains all numbers from $0$ upto $n$ with no duplicates.

The indices in $s$ indicate where the elements in $d$ need to go. So the element at $d[q]$
needs to be at $d[s[q]]$ where $n > q \geq 0$.

The goal is to find the minimum amount of $q \in \mathbb{N}$ swaps such that the after all swaps are performed the above holds.


texts: General question on choosing an Assembly language based on my goal

texts:
So I know assembly is so big and it seems learning assembly is like learning high level programming, you don't need to learn them all, you can learn couple and this will be enough.

The thing is with high-level language it is easier to grasp and implement in your life. But I am having hard time with assembly, I learned ARM at university, but I am not sure which version it was. And, it wasn't practical in real life. Also, it was too primitive. It doesn't even help me read other assemblies. Because when i read other assembly, I am lost seeing too many new commands that I have never seen before.

But I want to learn a language where I can add it to my code or make stand-alone version out of it easily like C++ or C# for Windows, so basically a practical language, also a language with live community and not an abandoned one.
i learned some programming languages and they are useless for me like CLIPS, ADA and Prolog.

So what are the useful and practical assembly languages out there to learn for windows. Is FAsm a good start? Also note that I do not know what I want to do with it, I will learn it them when I get good command of it I will decide, I may use it for images, or AI project or anyother use where my path will lead. I already know C++ (i use it for UE4 and AI code implementations), C# (desktop/web) app and java (desktop).


texts: How to achieve Dijkstra's O(X+Y) in time complexity if edge weights always is 1 or 2?

texts: If we were to have a connected directed graph that has X edges and Y vertices and all the edge weights are either 1 or 2. Would it be possible to somehow achieve a time complexity of O(X+Y) using Dijkstra's algorithm, when finding the shortest path between the two given vertices A and B from the graph.


texts: Why is a quantum computer not capable of solving more problems than a classical computer?

texts:
On the Wikipedia page for quantum algorithm I read that

  [a]ll problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are undecidable using classical computers remain undecidable using quantum computers.

I expected that the fundamental changes that a quantum computer brings would lead to the possibility of not only solving problems that could already be solved with a classical computer, but also new problems that could not be solved before. Why is it that a quantum computer can only solve the same problems?


texts: Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks?

texts:
Python quite famously uses indentation to syntactically define blocks of code. (See Compound statements in the Python Language Reference). After years of using Python I'm still intrigued by and very fond of this syntax feature.

But I wonder: Apart from Python and its "predecessor"(*) language ABC which other programming languages are out there using indentation for definition of code blocks? Code blocks means here "multiple statements which in some way are treated as one component".

I'm particularly interested in practical programming languages, but esoteric languages might be worth mentioning as well.

(*): "Predecessor" is my choice of word in default of knowing here a better one. Guido van Rossum, the creator of Python, described the relationship between Python and ABC regarding indentation in an interview like this: "The choice of indentation for grouping was not a novel concept in Python; I inherited this from ABC."


texts: What happens internally when you remove an object from a treemap

texts:
I am wondering what happens if you remove an object in the middle of a treemap.
If the treemap would look something like this:

So what would happen if you remove the number 30? Because 27 and 34 will disconnect from the tree.


texts: Calculate the average Big O from a function?

texts:
I was given this function: $T(N) = 3N\log^2 N + 5N^2\log N + \log N + 17N + 2$ and was asked to find the average Big O complexity.

If the Big(O) deals with an upper bound, would this algorithm be $O(N^2\log N)$ on average? But, because Big O is an upper bound, couldn't this also be $O(N^3)$, $O(N^4)$, etc.? Basically, is there a difference between Big O complexity and average Big O complexity of an algorithm?


texts:
So at the beginning I was aiming at $L_{a\neq b} = \{w\in \{a,b\}^* : \#_a(w)  \neq \#_b(w) \}$. But figured out that is would be better to first deal with: $L_{a>b} = \{w\in \{a,b\}^* : \#_a(w)  > \#_b(w) \}$, due to the fact that $L_{a>b} \cup L_{b>a} = L_{a\neq b}$.

My attempts so far for $L_{a>b}$ - I proved that this language is pump-able:
Choosing $N=2$ For $z\in L$ contains only $a$s the pump it pretty basic, on the other hand words contain $b$s: $\#_b(z) > 0 \Rightarrow \#_a(z) > \#_b(z) >0  $ so $z$ must include the couple $ab$ or $ba$ as a sub string, so $ z= \gamma ab\delta \Rightarrow \gamma|a|\varepsilon|b|\delta$ is a valid splitting, and $\gamma a^ib^i\delta\in L$ because the relation between $a$'s and $b$'s appearances is preserved.

So I was hoping this language might be context free and tried to form a Grammar which generates the language, However I didn't succeed in it, due to the fact that a general word of the form: $a^{i_1}b^{j_1}a^{i_2}b^{j_2}...a^{i_n}b^{j_n}$ when $i_k,j_k \in \mathbb{N}\cup\{0\}$ satisfies $\sum i_k > \sum j_k$ and I am having hard time dealing with cases in which $i_l <j_l$ (for example $aaaababb$ when the second pair is $abb$).

I don't know whether I may proceed from my best attempt, yet, in case  $ z = a^{i_1}b^{j_1}a^{i_2}b^{j_2}...a^{i_n}b^{j_n}$ satisfies $i_k > j_k \forall k\in [n]$ The grammar $A\rightarrow a | AA|AAB|BAA , B\rightarrow b$ with A as the initial term, should work (I didn't formally prove it so I might be wrong).

I also tried to work with closure properties but couldn't even find an idea to start with...


texts: How do I solve this function using basic instructions?

texts:
The function $f$ takes two integers and produces one integer

$f(a,b) \vdash 3*(b-a)$

The only instructions I can use are +1, -1, and go to loop

At a high level, I know how to write $z = 3*(a,b)$


texts: Are there any type constructors which are *not* functors?

texts:
So I'm almost done teaching myself category theory. One of the main take-aways for me is that type constructors (higher-kinded types) are endo-functors.

But it this always the case? What's throwing me off is Haskell's Functor typeclass:

class Functor f :: * -> * where
   fmap :: (a -> b) -> (f a -> f b)

If all type constructors were a priori functors, there would be no need to define a special type-class. But I can't think of any type-constructors that fail to satisfy the Functor type-class: product, sum, function, list, set, option, etc.

I also cannot imagine the utility of a type-constructors that is "one-half" of a functor, i.e. it has a map from objects to objects, but no map between morphisms.


texts: Algorithm to check two binary expression trees for equivalence

texts:
Is there any known algorithm to check for equivalence of two binary expression trees over a field $\mathbb{F}$?
For example for the expression $a+b = b+a$ it should return true (since $\mathbb{F}$ is commutative) and $a^b = b^a$ should return false as well as for $a^2 = a$.
I can think of a naive implementation which is basically brute-force creating all equivalent binary expression trees for LHS and for RHS and check for a non empty intersection.
Is there a real-world-efficient algorithm to do this? I mean it isn't a must to be polynomial time but will work fast for common or relatively small problems (trees with at most ~100 nodes).
Wikipedia doesn't give any reference to the problem of comparing two for equivalence over some algebraic structure.


texts: Is there a data-structure which is more efficient than both arrays and linked lists?

texts:
Background:
In this question we care only about worst-case running-time.
Array and (doubly) linked lists can be used to keep a list of items and implement the vector abstract data type. Consider the following three operations:

$Location(i)$: returns a pointer to the $i$th item in the list of items in the array.
$Insert(k,x)$: insert the item $k$ in the list after the item pointed to by $x$.
$Delete(x)$: remove the item in the list pointed to by $x$.

The main operation that an array provides is location which can be computed in constant time. However delete and insert are inefficient.
On the other hand, in a doubly linked list, it is easy to perform insert and delete in constant time, but location is inefficient.
Questions:
Can there be a data structure to store a list of items where all three operations are $O(1)$? If not, what is the best worst-case running-time that we can achieve for all operations simultaneously?
Note that a balanced binary search tree like red-black trees augmented with size of subtrees would give $O(\lg n)$, is it possible to do better? Do we know a non-trivial lower-bound for this problem?


texts: Knapsack Problem with exact required item number constraint

texts:
How would we solve the knapsack problem if we now have to fix the number of items in the knapsack by a constant $L$? This is the same problem (max weight of $W$, every item have a value $v$ and weight $w$), but you must add exactly $L$ item(s) to the knapsack (and obviously need to optimize the total value of the knapsack).

Every way I've thought of implementing this so far (dynamic programming, brute force) has resulted in either failure, or lifetime-of-universe level computation times. Any help or ideas are appreciated.

Edit: I am looking for pseudo-polynomial time solutions


texts: Correct implication for 3SAT from this theorem?

texts:
Theorem. Let none of the assignments of length $\log n$ make a set of unsatisfiable 2-clauses. Then formula is satisfiable.

$n$ is input length here.

Let we name an assignment that make the formula to contain unsatisfiable 2-SAT contradictive.

This allows us to find all minimal contradictive assignments in $O(n^{\log n})$ time. And we can make a new formula. However, if formula we got is not in $P$, can we say, that original formula is satisfiable?

Example of one is just unsatisfiable full CNF that has $\log n$ variables involved.

Second example is $x_1\land(\overline{x_1}\lor x_2)\land...\land(\overline{x_1}\lor...\lor x_{k-1})\land(\overline{x_1}\lor...\lor\overline{x_{k-1}}\lor x_k)\land(\overline{x_1}\lor...\lor\overline{x_k})$. This formula is Horn CNF and solvable in linear time.

Trying to solve this in a way of generating formulas.

Let we have a formula $f$ from class $P$ and a set of 2-clauses $g$.

Then, moving literals from $f$ to $g$ and negating them will allow to generate any 3SAT instance.

If $f$ is Horn SAT, then resulting formula will not have any restrictions that Schaefer's dichotomy theorem says. E.g. there can be both Horn and dual Horn clauses of length 3, which are not combined to XOR clauses.

This made me more sure that conjecture is true. And now I even think that if it is impossible to find Horn SAT that implies contradiction, then formula is satisfiable. Of course, finding such Horn formula takes polynomial time.


texts: Show that the pumping lemmas for context-free and regular languages are equivalent for unary languages

texts:
I want to show that for any language $L \subseteq \{ a \}^* $, $L$ satisfies the pumping lemma for context free languages if and only if it satisfies the pumping lemma for regular languages.

I know that every regular language is also a context free language so I tried to show that direction of the proof first but ran into some difficulties.

Is there a more logical approach to this? Would I have to show that the conditions for both the pumping lemma for regular languages and the pumping lemma for context free grammars are equivalent for this language?


texts: Computability of equality to zero for a simple language

texts:
Suppose we have a tree in which leaves are labeled with a set of numbers $L$, and internal nodes with a set of operations $O$.

In particular $L$ can be $\mathbb{N}, \mathbb{Z}$ or $\mathbb{Q}$, and can optionally contain $\pi$ and/or $e$.
$O$ can be any subset of $\{+,-,\cdot,/,\hat\ \}$.

Is equality with zero decidable? Are sign comparisons decidable? If so, are they feasible?

"Invalid" operations ($0/0$, $0^0$, ...) produce $NaN$, $NaN \neq 0$ and $NaN$ propagates through computations as usual.

Some combinations are trivial: if we restrict ourselves to field operations, and don't include either $\pi$ or $e$ in $L$ then we can just compute the resulting fraction and be done with it. Or if we restrict to $\mathbb{Z} \cup \{\pi\}$ and $\{+,-,\cdot\}$ we can compute the polynomial and check the coefficents. On the other hand powers (and hence $n$-th roots) and $\pi$ and $e$ make things considerably harder.

The "equality with zero" problem is an instance of the constant problem.


texts:
Why is the worst scenario $\mathcal{O}\left(n^2\right)$ when using quicksort to find the median of a set of numbers?

If your algorithm continually picks a number larger than or smaller than all numbers in the list wouldn't your algorithm fail? For example if the list of numbers are:

$S = (12,75,82,34,55,15,51)$

and you keep picking numbers greater than $82$ or less than $12$ to create sublists with, wouldn't your set   always remain the same size?
If your algorithm continually picks a number that creates sublists of $1$ why is the worst case scenario $\mathcal{O}\left(n^2\right)$? Wouldn't efficiency be linear considering that according to the Master Theorem,  $d>\log_b a$?* (and therefore be $\mathcal{O}\left(n^d\right)$ or specifically in this case $\mathcal{O}\left(n\right)$)

*Where $d$ is the efficiency exponent (i.e. linear, exponential etc.), $b$ is the factor the size of problem is reduced by at each iteration, $a$ is the number of subproblems and $k$ is the level. Full ratio: $T(n) = \mathcal{O}\left(n^d\right) * (\frac{a}{b^d})^k$


texts: Showing the predicate $n \leq \sqrt2 < n+1$ is primitive recursive

texts:
Let h(x) be the integer n such that $n \leq \sqrt2 < n+1$ Show that h(x) is primitive recursive.

I know how primitive recursive functions are defined, but showing an integer is primitive recursive is throwing me off. I need some help starting the proof.


texts: What does Tarski's Fixed-Point theorem give us that that Y-Combinator does't

texts:
I'm taking a graduate course on the theory of functional programming, based on Paul Taylor's "Practical Foundations of  Mathematics." I understand the statement of Tarski's theorem about how for any $\omega$-compelte poset $X$, and any $\omega$-continuous function $T:X\rightarrow X$, that $T$ has a fixed point which is the join of (The statement and proof can be found here).

What I want to know is, how is this applicable, other than being a proof that the Y-combinator exists? It just seems to me that it says "we can use recursion to build a function that is defined for all natural numbers", where we could use some other recursive type for numbers. Doesn't the existence of the Y-combinator show the same thing?


texts: Ways to perform "batch" Approximate Member Queries efficiently

texts:
In this problem, I'm first given n number of values which I have to store in a space efficient manner. Then I'm given m number of values which I have to check if they were added to the data structure before (such that after the operation, I know which value was a member, and which weren't).

I could use a Bloom Filter and simply iterate through m, but because m is considerably large, I wanted to see if there are more efficient ways. One potentially exploitable property of the data is that most values will not be present. I'm thinking I could construct an "aggregated query" which tells me if any of the value is present or not in one operation, and do something like a binary search, but wanted to see if there is already something out there.

Some additional details:

I can tolerate both false positives and false negatives (with predictable error rate)
n is very large (trillions)
m is considerably large (millions)
Only very few values in m will be members (ca. 1 in 100K)
The data structure can be immutable (no need for frequent writes)


texts: Time complexity of a problem inspired by palindromes

texts:
This was inspired by Bradshaw's question originally posted on Math.SatckExchange.

EVEN PALINDROME:

Input: Given a list of strings $[v_1, v_2, ... ,v_n]$ where $\Sigma |v_i| $ is even number.

Question: Is there a permutation $\sigma$ such that $w=v_{\sigma(1)}v_{\sigma(2)}... v_{\sigma(n)}$ $\in \{uu^R \in \Sigma^* \}$.

  Is it NP-complete to determine if a given set of strings can be ordered to form a palindrome (of even length as defined above)? If yes, Is it still NP-complete for $|\Sigma|=2$?

EDIT: Marzio has given an elegant reduction which shows that Even Palindrome is NP-complete for binary alphabets.


texts: Creating admissible heuristics from functions?

texts:
I'm having trouble figuring out how to create admissible heuristics from cost functions.  For example, if I was trying to create an admissible heuristic from a cost function that takes in starting position and ending position and returns the cost based on differences in height, I don't understand how to create an admissible heuristic from such a basic function.

Any help would be greatly appreciated.


texts:
Sorry this is a basic question to understand decidability. It is the first time I see it in my undergrad course.

1)
I am reading why the language AFDA is decidable and why ATM (halting problem) is not. The explanation says that the emulated TM in ATM might loop forever. I agree, because a specific input string might make the TM going forever, always able to apply rules and never halting.

However, why is AFDA decidable? What if the automaton never reaches any of its final states and keeps looping? There might be a specific input that makes the FDA never reach such states. I understand that once the input string finishes, it will be either accepted or rejected, but what if it does not finish? I'm assuming the input string in the TM can be infinite.

2)
The same problem I have here:

A = { 0^k 1^k | k >= 0}

This language is decidable, and it will halt in strings like 10, 010101, etc but what if the input string is infinite 01010101...... it will never end.

What am I missing?


texts: How to reduce $\{w \mid |T(M_w)| \geq 42\}$ to the halting problem?

texts:
For a string $w$, $M_w$ denotes the Turing machine whose encoding is $w$.

I want to reduce the language $L=\{w \mid |T(M_w)| \geq 42\}$ to $H_0 = \{w \mid M_w \text{ halts on } \epsilon\}$, but I can't find a way to define an algorithm that halts only if $w \in L$. Either way:

if $w \in L$ I would have to find at least 42 words that are in $T(M_w)$, which might be undecidable for certain languages.
if $w \notin L$ then $M_w$ would accept only 41 or less words. Then we do know, that the language $T(M_w)$ is regular, but still we can't test if the language is regular or not.

Simply trying random words until we have at least 42 doesn't work as for some words the TM will not halt.

Is there any idea I could try? Or in other words: how would one prove $L \leq H_0 $?


texts: There is equivalence in an NP-hardness proof or not?

texts:
I want to show that some problem $P_1$ is NP-hard. I have a problem $P_2$ that is NP-complete. From an instance of $P_2$ I created in polynomial time an instance of the problem $P_1$.

My question is: Should I verify both direction ($\Leftrightarrow$) or only one direction ($\Rightarrow$)? More precisely, which one to show from these two:

Solve $P_1\;\Leftrightarrow$ solve  $P_2$
Solve $P_1\;\Rightarrow$ solve  $P_2$


texts:
Let $\Sigma = \{a, b\}$. For each of the following languages, find a grammar that generates it.

(a) $L_1 = \{a^n b^m : n\geq 0, m>n\}$

(b) $L_1^3$

(C) $L_1^*$

I know the grammar for the language $L_1$, that is

$S \rightarrow aSb \mid bA$
$A \rightarrow bA \mid \epsilon$

please help me to find the grammars for another two languages.


texts: Articulation vertex in complementary graph

texts:
I need to implement an algoritm, but I can't understand the theory behind it.

How can I prove that if v is an articulation vertex in a graph G , that it will not be an articulation vertex in G' complimentary graph ?

I know that an articulation vertex , is one which when removed disconects the G . And that the complementary graph , is one with two distinct vertices adjacent if and only if they are not adjacent in G.But I can't figure out how to connect this statements with my problem.


texts: O(n) time algorithm for maximum earnings

texts: There are $n$ plates $p_1$ to $p_n$ each filled with money of value $a_1$ to $a_n$. You can take the money from one or more plates if the sum of the money in them is divisible by three. I need a $\mathcal{O} (n)$ asymptotic time logarithm for finding the maximum earnings that can be achieved. I have no idea for such a fast algorithm, so any help is welcomed.


texts: I have a timeseries dataset of a quantity measured over the period of a week. I want to verify if the data is varying in a diurnal fashion with the help of some mathematical measure. Does any such measure exist?


texts:
I am confused about the precise definition of the DPLL algorithm. Various sources tend to define DPLL differently:

In pages 110-114 of the book Handbook of Satisfiability(Editors: Biere, A., Heule, M., Van Maaren, H., Walsh, T. Feb 2009. Volume 185 of Frontiers in Artificial Intelligence and Applications) it defines it as backtracking + unit propagation.

Also can be accessed from: http://reasoning.cs.ucla.edu/fetch.php?id=97&type=pdf (pages 106-110).

In wikipedia: https://en.wikipedia.org/wiki/DPLL_algorithm#:~:text=In%20logic%20and%20computer%20science,solving%20the%20CNF%2DSAT%20problem.
it defines it as backtracking + unit propagation + pure literal elimination.

And in original 1962 paper: https://archive.org/details/machineprogramfo00davi/page/n5/mode/2up
it mentions 3 rules: one-literal clause rule(unit propagation), affirmitive-negative rule(pure literal elimination) and rule for eliminating atomic formulas(creating resolvents).

Therefore, I am looking for a clear and strict definition of DPLL algorithm. Maybe it should be considered as purely backtracking algorithm and unit propagation and pure literal elimination as its extensions? Or maybe unit propagation is essential part of the algorithm and pure literal elimination is considered to be extention..?


texts:
Say we have some BNF rules for example:

$$A ::= B C$$
$$Dx ::= ExFx$$
$$x ::= y$$

So we might start with $Dx$ and apply rule 2 to get $Ex Fx$ and then apply rule 3 to get $Ey Fy$. But starting with $Dy$ we can't get anything. Unless...

What if we extend the BNF rules to let the rules apply to other rules. Then we could take rule 3 and apply it to rule 2 (interpreted as a string) to get a new rule:

$$Dy ::= EyFy$$

My question is, if we allow such creation of new rules like this. What kind of grammar do we end up with? What is the name of it? Is it equivalent to church lambda calculus?

Using these rules we could express the grammar where the quantity matches the noun and determiner like this:

$$amount ::= singular|plural \\
NP(amount) ::= det(amount)\ \ noun(amount) \\
det(singular) ::= a | one \\
det(plural) ::= some | two | three \\
noun(singular) ::= cat | dog \\
noun(plural) ::= cats| dogs
$$

From which we would get $some\ cats$ and $one\ dog$ for example.


texts:
I want to reduce $MAX3SAT$ to $MAX2SAT$ ...
MAX-n-SAT : given $\phi $ n-CNF formula and number k does $\phi$ has an assignment that satisfy k clauses?


texts: Deleting edges such that largest connected component has at most $n/4$ nodes

texts:
Let $G = (V, E)$ be a connected undirected graph with $n > 4$ nodes $V = \{v_1, v_2, \dots, v_n\}$ and $m$ edges.
Let $\{e_1, e_2, \dots , e_m\}$ be all the edges of $G$ listed in some specific order. Suppose that we remove the edges from $G$ one at a time, in this order. Initially, the graph is connected, and at the end of this process
the graph is disconnected. Therefore, there is an edge $e_i$ such that just before removing $e_i$ the graph has at least one connected component with more than $n/4$ nodes, but after removing $e_i$ every connected component of the graph has at most $n/4$ nodes.

Give an efficient algorithm that
determines this edge $e_i$. Assume that $G$ is given to the algorithm as a plain linked list of the edges appearing in the order $e_1, e_2, \dots, e_m$.
The worst-case running time of this algorithm must be asymptotically better than $O(mn)$.


texts: Can we create faster sort algorithm than O(N log N)

texts:
I was thinking that we can create algorithm for sorting that will work faster than $O(N\log N)$

Let's say we have given array $A$ consisting of $N$ integers, where $N = 10^6$. Our task is to sort this given array. The clear solution is to sort the array using the classic merge sort algorithm, which works in $O(N \log N)$ time and space complexity. I was thinking that this trick can improve the complexity.

Let $N_{1} = 10^5$, clearly $N = 10\cdot N_{1}$. Let's split the array $A$ in $10$ smaller array where each array consist of $N_{1}$ elements and sort those $10$ arrays with standard merge sort ( time complexity: $O(N_{1}\cdot\log N_{1})$), so we have 10 arrays where each array is sorted, we can merge those 10 array into one array in time complexity $O(N\cdot\log(10))$ using priority queue.

So the total complexity will be $O(10 \cdot N_{1}\cdot\log N_{1} +N\cdot\log(10))$. Now let's say we split the array in $\sqrt{N}$ arrays, so the complexity will look like: $$O(\sqrt{N} \cdot \sqrt{N} \cdot \log \sqrt N + N \cdot \sqrt N)\\ = O(N \cdot \log (\sqrt N) + N \log (\sqrt N))$$

Is everything in my algorithm correct, and is this trick efficent in memory usage?


texts: Lossless data compression must make some messages longer?

texts:
I read on Wikipedia and in lecture notes that if a lossless data compression algorithm makes a message shorter, it must make another message longer.

E.g. In this set of notes, it says:

  Consider, for example, the 8 possible 3 bit messages. If one is
  compressed to two bits, it is not hard to convince yourself that two
  messages will have to expand to 4 bits, giving an average of 3 1/8
  bits.

There must be a gap in my understand because I thought I could compress all 3 bit messages this way:

Encode: If it starts with a zero, delete the leading zero.
Decode: If message is 3 bit, do nothing. If message is 2 bit, add a
leading zero.
Compressed set: 00,01,10,11,100,101,110,111

What am I getting wrong? I am new to CS, so maybe there are some rules/conventions that I  missed?


texts:
(If I am posting this in the wrong StackExchange site, then please direct me to the correct one)

Okay, so some small background first: I am currently third-years student in Computer Science on the university.

I have big interest in Artificial Intelligence and I was wondering if I could practice it somewhere, for example a challenge versus other people that gets updated/executed every set time period (possibly per week).

Example of a challenge that I do like:

Assume that there is an infrastructure set by the organisator to run a poker game via poker bots. I would like to code such a poker bot that would challenge other people, by using AI via a statistical approach, but also via doing fake moves, remembering what the other players have done so far.

It could even be fun to add in real players and see who wins in the end.

Example of a challenge I do not like:

Given a partially filled in Sudoku puzzle, make an algorithm that solves the puzzle.

Why don't I like the Sudoku? Well, I would rather challenge other players or have an interactive way of using AI. I don't even think that an algorithm like this involves any AI. However when asked to do this exercise as part of my study, I didn't mind it, because it was still an interesting programming problem.

Has anyone else been in the same boat? Or is someone being in the same boat currently?

Please share any thoughts, I definately would like to practice around with this, but for example doing the poker bot thing just by myself would be somewhat... dull.

Regards.

edit: Forgot to add, but for a challenge or anything I would prefer Java, as I am used to doing that. But any raw format (so just sending data to a channel and receiving data from a channel would also do)


texts: Proving or disproving a set of total functions is countable

texts:
Let S be the set of total functions from $N \rightarrow M$, such that for each $f \in S$, there is $i > 1$ such that for
  all $j < i$, $f(i)$ and $f(j)$ are not equivalent Turing machines. Prove or disprove that S is countable

I don't think this is actually countable, but I'm having a hard tie proving this using diagonilzation. Can anyone give me pointers / hint? Preferably explained at a lower level.


texts:
The following is what I came up with from my synthetic prior research but I might be wrong.

I understand it is possible to reduce any computer "program", in a maximal reduction(?), to these features:

Internal implementation: Everything from start to end, including possible functions and possible sub functions
External interface: A parameter set with which arguments might correspond in execution or call → if any

Internal implementation includes:

Data structures: Primitive data types and possibly also functions or modules (depends what term one prefers)
algorithms: outside or inside a function/algorithm → if any
Database interfaces → if any

I understand that external interface (very often represented by parenthesis) can be part of internal implementation (which, in programming languages, is very often represented by brackets) and that yes or no depends from language architecture.

IS there a consensus on the definition of a computer program in CS literature and if so, what is it?