texts: Upper Bounds on Characteristic Path Length of Graphs

texts:
Characteristic (average) path length is defined here: https://cs.stackexchange.com/a/7538/20256

I want to establish upper and lower bounds on the CPL for a graph of $n$ vertices, and any positive number of edges, such that each vertex has a degree of at least 1 (i.e. the graph is connected). Assume that the graph is undirected, and unweighted.

My initial guess on the upper bound was a "straight line" of vertices, i.e.:

1 -- 2 -- ... -- n-1 -- n

with edges denoted as "--".

Working through the calculations, I arrived at the value for the CPL of this graph to be $\frac{n+1}{3}$. However, I cannot come to a proof on this being the absolute upper bound.

Also, what would a lower bound be? I conjecture that a regular graph (http://en.wikipedia.org/wiki/Regular_graph) would be the correct answer, but haven't found a proof for this either.

Edit: the lower bound is 1. The reason is construct a fully connected graph (i.e. any vertex is connected to all other vertices by 1 edge).


texts: Heap - Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list

texts:
Most probably, this question is asked before. It's from CLRS (2nd Ed) problem 6.5-8 --

  Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: Use a min-heap for $k$-way merging.)

As there are $k$ sorted lists and total of $n$ values, let us assume each list contains $\frac{n}{k}$ numbers, moreover each of the lists are sorted in strictly ascending order, and the results will also be stored in the ascending order.

My pseudo-code looks like this --

    list[k]   ; k sorted lists
    heap[k]   ; an auxiliary array to hold the min-heap
    result[n] ; array to store the sorted list
    for i := 1 to k                 ; O(k)
    do
        heap[i] := GET-MIN(list[i]) ; pick the first element
                                    ; and keeps track of the current index - O(1)
    done
    BUILD-MIN-HEAP(heap) ; build the min-heap - O(k)
    for i := 1 to n
    do
        array[i] := EXTRACT-MIN(heap)   ; store the min - O(logk)
        nextMin := GET-MIN(list[1])     ; get the next element from the list 1 - O(1)
        ; find the minimum value from the top of k lists - O(k)
        for j := 2 to k
        do
            if GET-MIN(list[j]) < nextMin
                nextMin := GET-MIN(list[j])
        done
        ; insert the next minimum into the heap - O(logk)
        MIN-HEAP-INSERT(heap, nextMin)
    done

My overall complexity becomes $O(k) + O(k) + O(n(k + 2 \lg k)) \approx O(nk+n \lg k) \approx O(nk)$. I could not find any way to avoid the $O(k)$ loop inside the $O(n)$ loop to find the next minimum element from k lists. Is there any other way around? How to get an $O(n \lg k)$ algorithm?


texts:
Special Turing Machine is defined just like standard Turing Machine, only that each step is made according to the content of the tape starting from the left edge to the head position in tape.
(The transition function in this case belongs to Q X Γ* -> Q X Γ X {L,R})

Which of the following is true:

A. Every language L has a Turing machine that decides L if and only if there is a special Turing machine that decides L.

B. Every language L has a Turing machine that decides L in a polynomial time if and only if there is an special Turing machine that decides L in a polynomial (input length polynomial).

C. A,B answers are correct.

D. A,B answers are incorrect.

and my question is:
the correct answer is D and I can't understand why.

The answer is:
Each language can be decided by a special Turing machine in linear input length time (O(n) when n is the input length). A transition function goes to the right as long as no blank space is seen, and as soon as you see a blank space switches to receiving or rejecting according to the word written on the tape.

My question is:
How can I decide whether to reject or accept a word?
In other computational models, such as PDA, DFA, we defined the transition function similarly, and no power was added to the model.
Why does it seem that power is added to the computational model as a result of the change of the transition function when it comes to Turing machines?

Thanks.


texts: Finding loop invariant of Lowest common multiple function

texts:
So I have the following function:

def lcm(a,b):
    x = a
    y = b
    while x != y:
        if x < y:
            x += a
        else:
           y += b
    return x

I'm not sure how I will go about finding the loop invariant of this question. I know I have to find some sort of relationship between $x$ and $y$ but nothing seems to hold or is helpful in actually proving correctness.


texts: Space complexity of boolean circuit evaluation

texts:
I am given a boolean circuit of depth $D \ge \log n$ where $n$ is the input size.
Given an input, I need to find an algorithm that evaluates the circuit in space $O(D)$.

Now, assuming the fan in of each vertex is at most 2, I can set 2 bits for each vertex, one for the value of the vertex, and the other for which of his sons I am currently evaluating. Where I am stuck is that I am not given any information on the fan out of each vertex, So I can't just set a value to know which parent to go back to when I finish evaluating a sub circuit.

I would like some help understanding the catch here.

thanks.


texts: Proving whether $\bf{K}$(Happy $\lor$Sad) $\implies$ $\neg \bf{K}($Happy) is satisfiable, valid or unsatisfiable

texts:
I have a question that I am stuck on reasoning about knowledge. For the following statement, I need to show whether it is valid, satisfiable or unsatisfiable:

$\bf{K}$(Happy $\lor$Sad) $\implies$ $\neg \bf{K}($Happy)

I have done the following:

Let e w be an interpretation where e is the set of possible worlds and w is the real world. Then we need to show that for any interpretation, e w satisfies  $\neg \bf{K}$(Happy $\lor$Sad) $\lor$ $\neg \bf{K}$(Happy).:

Now assume that such an interpretation e w satisfies  $\bf{K}$(Happy $\lor$Sad). This would mean for all w' $ \in$ e, e w' satisfies  $\bf{K}$(Happy $\lor$Sad). However in a world w'' = {$\neg Happy, \neg Sad$}, then the interpretation e w'' does not satisfy  $\bf{K}$(Happy $\lor$ Sad).

Therefore, we have a contradiction and for any interpretation e w, e w satisfies $\neg \bf{K}$(Happy $\lor$Sad).

Similarly, assume an interpretation e w satisfies $\bf{K}($Happy). However, if we have a world(s) where $\neg$Happy is true, then e w'' does not satisfy  $\bf{K}($Happy). Therefore for any e w, e w satisfies $\neg \bf{K}($Happy) and thus the statement is valid.

I'm not sure whether my proof is correct and if not, could give me a hint on how to go about with this question.


texts: Knight's tour from all starting positions

texts:
Is it true that for all $n\geq 5$, there is a knight's tour of an $n\times n$ chessboard beginning at every square?

For example, is it correct, that there is no solution for a $5\times5$ board,
with start position $(5,4)$?


texts: Lower bound on number of comparisons needed to search for a number in a sorted 3-d array

texts: Suppose we have an $N \times N \times N$ 3-d sorted array meaning that every row,column, and file is in sorted order. Searching for an element in this structure can be done using $O(N^2)$ comparisons. However are $\Omega(N^2)$ comparisons needed in the worst-case? For an $N \times N$ 2-d sorted array I recall a proof that $\Omega(N)$ comparisons are needed; I'm having trouble seeing how to extend to the 3-d case though


texts: Can a context free grammar for $L$, generate a string not in $L$?

texts: from Sipster's definition: Any language that can be generated by some context-free grammar (call it $G$) is called a context-free language (CFL). However, can $G$ generate strings that are not in the the language that recognizes $G$?


texts: What is an efficient data structure for prefix matching?

texts:
I'm looking for an data structure that supports efficient random prefix matching queries (pattern) over a previously known set of words (dictionary). The dictionary is expected to contain about 10,000 words of varying length (I haven't calculated average word length, but I don't expect any word to be more than 80 characters long). Prefix matching in this case would be equivalent to words[i].toLowerCase().startsWith(pattern.toLowerCase()).

A Trie is an obvious choice, and provides linear time search corresponding to the length of the pattern. However, I'm confused whether a Suffix Tree, or a Suffix Array, might provide any improvements over a Trie. It seems a Suffix whatever is commonly used for one text, not multiple. I also have no requirement for supporting the various cool use cases (longest common prefix, or number of times a prefix occurs etc) that Suffix whatever can efficiently support.

I'm looking for a recommendation on which data structure to use, and why. Tries use a lot of space, and if I end up using one, I'd consider compress the branches with nodes with outdegree 1.

For the duplicate button happy readers, I've read this and this question, none seemed directly relevant.

Example:

Dictionary: [banana, apple, banter, orange]

Pattern: ban
Return: banana (any match)

Pattern: grapes
Return: null


texts: What are the tradeoffs in compiler development effort related to CISC vs. RISC?

texts: What advantages and disadvantages does a CISC instruction set have relative to a RISC instruction set with respect to the ease of developing a functioning compiler and the ease of developing a highly optimizing compiler?


texts: Is there an algorithm to detect race conditions in logic circuits?

texts:
I'm writing a logic gate simulator. I would like to prevent user from constructing circuits prone to race condition such as flip-flops, and instead provide them as separate building blocks. Is that possible?

edit: I've got an idea. I guess that race conditions can only arise from logic circuit outputs directly or indirectly affecting their own inputs. So one way to check their validity would be to compare the truth tables of their inputs and outputs.

example one: NOT gate feeding itself

    A = !A
A | A   A | !A
--+--  ---+---
T | T   T | F
F | F   F | T
the truth tables do not match!

example two: SR NOR latch

!(A || B) = C
!(C || D) = B
!((!(A || B)) || D) = B // C => !(A || B)

 A | B | D | !((!(A || B)) || D)           B | B
---+---+---+--------------------          ---+---
 F | F | F |          F                    F | F
 F | F | T |          F                    F | F
 F | T | F |          T                    T | T
 F | T | T |          F (wrong!)           T | T
 T | F | F |          T (wrong!)           F | F
 T | F | T |          F                    F | F
 T | T | F |          T                    T | T
 T | T | T |          F (wrong!)           T | T

I hope you understand what I'm trying to convey. However, I have nothing to back it up, and I struggle to define it into an algorithm, and even if I could, it would have horrible complexity. I will try to refine it tommorow.

online truth table generator tool I used

edit 2: this is what I found in logisim manual:

  Logisim will not attempt to detect sequential circuits: If you tell it
  to analyze a sequential circuit, it will still create a truth table
  and corresponding Boolean expressions, although these will not
  accurately summarize the circuit behavior. (In fact, detecting
  sequential circuits is provably impossible, as it would amount to
  solving the Halting Problem. Of course, you might hope that Logisim
  would make at least some attempt - perhaps look for flip-flops or
  cycles in the wires - but it does not.) As a result, the Combinational
  Analysis system should not be used indiscriminately: Only use it when
  you are indeed sure that the circuit you are analyzing is indeed
  combinational!

However, the amount of inputs and outputs here is finite and well defined, as opposed to infinite memory and time resources in the Halting Problem, so I do not agree that this problem is equivalent to the Halting Problem.


texts: Proof on lower bound of search in unsorted array with information theory?

texts: I know there are proofs using an adversary technique. I've seen other proofs for search in a sorted list using information theory. But I haven't come across a proof using it to prove the lower bound for a search in an unsorted list using information theory.


texts: Polynomial Computation of the probability of a number of independent events

texts:
Suppose to have $n$ independent events $E_1, E_2,..., E_n$, where the probability of occurrence of event $E_i$ is $p_i$ (i.e., each event has its own probability of occurrence). We can easily define new events of type $N_k\equiv$"exactly $k$ events occur".

The probability of event $N_k$ can be computed as
$$\Pr(N_k) = \sum_{I \in \mathcal{I_{n,k}}}\prod_{i \in I}p_i \prod_{i \notin I} (1-p_i)$$
where $\mathcal{I_{n,k}} = \lbrace I \subseteq \lbrace 1,2,\ldots,n \rbrace :|I|=k \rbrace$. However, this calculation requires exponential time w.r.t. $n$.

Is there an algorithm with polynomial time complexity w.r.t. $n$ to compute the probability of each $N_k$, for $k=0,1,...,n$?


texts:
Are there problems that are in NP class but not in #P class?
According to Wiki definition:

  More formally, #P is the class of function problems of the form "compute ƒ(x)," where ƒ is the number of accepting paths of a nondeterministic Turing machine running in polynomial time"

So I am thinking, if you already have a poly nondeterministic Turing machine that can accept correct paths, then you can just use this to count in poly time.
Is there something I am missing here?


texts: Variance of MAXSAT clause satisfiability

texts:
For a given MAXSAT problem, it is trivially easy to compute the mean number of clauses satisfied for all assignments, or equivalently the expected number of clauses satisfied by a random assignment.

Is it likewise possible to compute the variance of the number of clauses satisfied? And I mean an exact computation, not an estimate.

In general, which moments are easy to compute, and which are hard?

I would prefer an answer for general MAXSAT but would also be interested in the special case of MAX-3-SAT.


texts: Why don't we use quick sort on a linked list?

texts:
Quick sort algorithm can be divided into following steps

Identify pivot.
Partition the linked list based on pivot.
Divide the linked list recursively into 2 parts.

Now, if I always choose last element as pivot, then identifying the pivot element (1st step) takes $\mathcal O(n)$ time.

After identifying the pivot element, we can store its data and compare it with all other elements to identify the correct partition point (2nd step). Each comparison will take $\mathcal O(1)$ time as we store the pivot data and each swap takes $\mathcal O(1)$ time. So in total it takes $\mathcal O(n)$ time for $n$ elements.

So the recurrence relation is:

$T(n) = 2T(n/2) + n$ which is $\mathcal O(n \log n)$ which is the same as in merge sort with a linked list.

So why is merge sort preferred over quick sort for linked lists?


texts: Description logics with decision problems within NP

texts:
Is there any description logic where important decision problems (e.g. abox consistency or concept satisfiability) lie within NP with respect to their time complexity?

The well-researched family of $\mathcal{ALC}$-based logics might not work since even for $\mathcal{ALC}$, problems are PSpace-complete. Neither would the $\mathcal{EL}$ family since the problems are at least CoNP.

Some restriction thereof might work, though, although I couldn't find any so far.


texts: Is the exact cover problem NP-hard when there is a restriction on the size?

texts:
The exact cover problem with restrictions on the size is:

Input: Given a set $U=\{1,2,\ldots,n\}$ and a collection of $C$ of subsets of $U$.

Question: Is there a subcollection $C^\star$ of $C$ such that

The intersection of any two distinct subsets in $C^\star$ is empty;
The union of the subsets in $C^\star$ is $U$; and
The size of any set $S\in C^\star$ is at most $\log_2 n$, i.e., $|S|\leqslant \log_2 n$ for all $S\in C^\star$.

Is this problem NP-hard?


texts: BigO, Running Time, Invariants - Learning Resources

texts:
What are some good online resources that will help me better understand BigO notation, running time & invariants?

I'm looking for lectures, interactive examples if possible.


texts: Proving B-Min-Cost Strongly connected Subgraph is NP-Complete

texts:
We have a strongly connected directed graph where each edge has positive integer weights. We are also given a $B \in \mathbb{N}$. Does there exist a strongly connected subgraph where sum of edge weights $\leq B$?
I'm not sure what NP-Complete problem to use. I tried subset sum, but it takes exponential time to build the graph I had in mind (yes/no tree with edge cost being the numbers in subset sum problem, and a final edge to root at end of every decision sequence). Any ideas? Is there a better NP-Complete problem to use?


texts: $L$ APX-hard thus PTAS for $L$ implies $\mathsf{P} = \mathsf{NP}$

texts:
If $L$ is an APX-hard language, doesn't the existence of a PTAS for $L$ trivially imply $\mathsf{P} = \mathsf{NP}$?

Since for example metric-TSP is in APX, but it is not approximable within 220/219 of OPT [1] unless $\mathsf{P} = \mathsf{NP}$. Thus if there was a PTAS for $L$ we could reduce metric-TSP using a PTAS reduction to $L$ and thus can approximate OPT within arbitrary precision.

Is my argument correct?

[1] Christos H. Papadimitriou and Santosh Vempala. On the approximability Of the traveling salesman problem. Combinatorica, 26(1):101–120, Feb. 2006.


texts: Is {a^n (a+b)^n | n>0} a Deterministic CFL?

texts:
$L = \{  a^n (a+b)^n   | n>0\}$

A book I'm reading says it is, but considering we can't know where the second part gonna start, and it might start with a as well, then how can we accept this using a DPDA? Like after reading the first part ($a^n$) how can we be sure that it's the end of the first part or not considering the second part can also start with $a?
$

Is this Deterministic?


texts: Dynamic Program to solve an NP-complete partitioning problem

texts:
I have this problem for which I am struggling to find an efficient dynamic programming algorithm. Would be thankful for some help!!

Let $A = \{ a_1, a_2, ..., a_n \}$ be a set where $a_i \in \mathbb{N}$ for $i=1,...,n$.

The goal is to determine whether there exist two disjoint subsets $M,N \subset A$ such that the sum of all elements in $M$ is equal to exactly $\textit{twice}$ the sum of all elements in $N,$ and $M \not = \emptyset$ and $N \not = \emptyset.$


texts: Finding farthest item in an array with duplicates

texts:
I have an array $A[]$ of size $L$, which contains numbers in the range $1 \ldots N$.  Here $L>N$, so the array will contain repetitions.  If $x,y$ are two numbers that are both present in the array, define the distance $d(x,y)$ to be the minimum difference in positions where $x,y$ appear, i.e.,

$$d(x,y) = \min \{|i-j| : A[i]=x, A[j]=y\}.$$

Given a number $x$ that is present in the array, I need to find the number $y$ in the array distance from $x$ is as large as possible.  In other words, given $x$, I am trying to find $y$ that makes $d(x,y)$ as large as possible (subject to the restriction that $y$ is a number in $A[]$).

Can this be done in $o(L)$ time per query?  It's OK to do some pre-processing of the array.

For example, suppose the array is $[1,3,2,3,4,5,3]$.  Then $d(5,3)=1$, since there is a $5$ one position away from a $3$ (a $5$ appears at index $5$ and a $3$ appears at index $6$).  If the query is $x=5$, the correct answer is $y=1$, since this makes the value of $d(5,y)$ as large as possible.


texts:
I read an example that said explain what "$f(n)$ is $n^{O(1)}$" means.

I can't interpret the $n^{O(1)}$ syntax. I know what Big $O$ notation is, its just that this example looks odd to me.


texts: Is $O(n^{1/2})$ exponential? Is $O(n)$ better than $O(n^{1/2})$?

texts:
I was just going through some of the primality test algorithms. It seems that the regular one – loop up to square root of $n$ – has running time $O(n^{1/2})$.

Is $O(n^{1/2})$ exponential? And is exponential time better than polynomial always?


texts: Select largest subset, subject to a separate weighting constraint

texts:
Given an unsorted set of tuples $(c, w)$ and a threshold value $W$, I want to select $k$ tuples such that:
$$
maximize\sum_{i=1}^k c_i \\
\sum_{i=1}^k w_i \ge W
$$
It seems pretty simple at first. Without the weighting constraint, you can use any selection algorithm to select the $k$ elements with largest $c$. But with the weighting, it seems there's no special structure to exploit. Seems like you'd have to search all subsets?


texts: Network flow - minimum flow through edge

texts:
In my max flow network, I would like to have an edge with upper bound of the flow (a.k.a. edge capacity) $c_{max}$. However, I would also like to add a lower bound for the flow through the edge, $c_{min}$.

I need to be sure that the minimum flow satisfies not only all the upper bounds (capacities), but also all the lower bounds.

Is it even possible? And if yes, which changes do I need to make to my flow network so that the max flow algorithm takes these lower bounds into account?


texts: Is there any language that can be Turing-reduced to all languages?

texts: I suppose not, but I do not have a clear way to prove it. Right now, I am trying to find a counter example that there exists a language that cannot be reduced from the language, but I am not sure if there is the right direction.


texts: Why on board graphics is unfit for gaming/rendering?

texts: What is the difference between a dedicated GPU and an integrated one?


texts: Chomsky NF or Greibach NF benefits for LR parser?

texts:
Are there any benefits of having grammar in CNF/GNF for LR parser? I have those in mind:

total speed of creating a parser (that is time for creating CNF/GNF out of the grammar, and then creating action table),
the size of action/goto table (in total)
is there any "side-effect" of removing some of shift-reduce conflicts

?


texts: Why can't one use the Cook-Levin theorem to show that TQBF is PSPACE-complete?

texts:
I have been reading Michael Sipser's Introduction to the Theory of Computation, and I have stumbled upon a paragraph in Chapter 8 (Theorem 8.9 on page 339 of the 3rd international edition) that I simply do not understand.
For context, TQBF is the language of all first-order logical formulas in prenex normal form that are true given a universe/domain.
A language $B$ is PSPACE-complete if

$B$ is in PSPACE, and
every $A$ in PSPACE is polynomial time reducible to $B$.

The following paragraph from the book tells us that it is a bad idea to use Cook-Levin theorem for the purpose of showing that a language $A$ in PSPACE is polynomial time reducible to TQBF. The paragraph reads:

As a first attempt at this construction, let's try to imitate the proof of the Cook-Levin theorem, Theorem 7.37. We can construct a formula $\phi$ that simulates $M$ on input $w$ by expressing the requirements for the accepting tableau. A tableau for $M$ on input $w$ has width $O(n^k)$, the space used by $M$, but its height is exponential in $n^k$ because $M$ can run for exponential time. Thus, if we were to represent the tableau with a formula directly, we would end up with a formula of exponential size. However, a polynomial time reduction cannot produce an exponential-size result, so this attempt fails to show that $A$ is polynomial time reducible to TQBF.

This last sentence I don't get. Why cannot a polynomial time reduction produce an exponential size result? Doesn't any reductions using Cook-Levin from an NP language result in an exponential-size result? Is it that it doesn't work in this particular situation, or is this a general thing?
My guess is that it has to do with the assumed space complexities of $A$ or TQBF, however I still don't see it. One of the conditions for TQBF's PSPACE-completeness is to show that any PSPACE language is polynomial time reducible to TQBF. Any talk about space shouldn't really belong.
Maybe it's my sheer interpretation of the sentence?


texts:
So I'm trying to figure out why the worst case of Quicksort is $O(n^2)$.
I know this a very well known problem, but the funny thing is where ever I look (even Wikipedia) gives the following explanation: "The worst case is the most unbalanced case where the problem splits to a problem of size $n-1$ and a problem of size $0$ (i.e. when the array is already sorted)".
Then they use the master theorem and find it is $O(n^2)$.
Marvelous. So simple. But wait.
Do we know upfront that the worst case is $O(n^2)$? No, that's what we need to prove.
"The most unbalanced case" meaning it is the worst case? Is there any theorem that states this?
So what is actually a coherent proof that Quicksort is $O(n^2)$?
Or in other words, what is the proof for the missing part?
We can derive that the run time can be described as $T(n) = T(n_1) + T(n_2) + O(n)$ where $n_1 + n_2 + 1 = n$. How to prove $T(n)$ is the largest when $n_1 = 0$ and $n_2 = n-1$?
I already know this is the most unbalanced case. Why is it actually the worst case?


texts: How to convert a decision table to a consistent decision tree?

texts:
I am working from presentation from school, but I am not able to understand how they go from one step to the other. This is the decision table that I have.

From it, the first thing we have to do is to choose the root node among these nodes:

But I do not understand why for example from Q1 the Y branch has a1, a2 and the N branch has a1,a3.

This is then the final solution for the tree:

I am not sure if this is the correct name in English, maybe that's the reason I wasn't able to find any literature online.

I would appreciate an explanation or at least a link to a guide on how to convert decision tables to optimal decision trees that are consistent with the decision table.


texts: single tape NTM to single tape DTM equivalence

texts:
I am having some trouble understanding the equivalence of DTM's and NTM's.
If you have Sipser its under 7.11; where he says that any NTM $N$ that halts after $t(n)$ steps has an equivalent DTM $D$ that halts after $2^{O(t(n))}$
steps.

He says that  $N$ 's "computation tree" has at most $b^{t(n)}$ leaves, where $b$ is the maximum number of choices a transition can have in $N$, and the tree is at most $t(n)$ "levels deep", since $N$ halts after $t(n)$ steps per definition.

Now if one would like to simulate $N$ with $D$ you would have to go through no more than $t(n)b^{t(n)}$ steps to halt.

Then Sipser says that $O(t(n)b^{t(n)})= 2^{O(t(n))}$ which I dont understand.

In my understanding the runtime of $D$ should be $O(b^{t(n)})$ where $b >0$.

Can someone clear this up for me ?

Relevant pages in Sipser are  255-256.


texts: Trying to find all possible combinations

texts:
I am trying to find all the combination of options trades that make the highest profit. Each trade has a maximum profit and maximum loss. I have a list of maximum losses e.g. [5298, 1100, 500]. Each number corresponds to a trade. The combination of maximum losses must be under the money I have in my account, for example, 9000. I'm trying to subtract each number in the maximum loss array from the money in my account and repeatimg it until it gets to 0 or a negative number. It then advances to the next number. This will miss many combinations because it doesn't try the first AND second AND third at the same time. Does anyone know of an algorithm or know how to find and algorithm to find such combinations or have a better idea than mine? This is the pseudocode I have come up with:

for loop through max loss array
find difference between moneyInAccount and max loss[0]
if difference > maxLoss[0] then
difference = difference - maxLoss[0]
or else index to next maxLoss
if maxLoss[1] > difference
then difference - difference - maxLoss[1]
and so on


texts: How can a TM M' have a property P if it only accepts a single string x from language of P?

texts:
Here is the document: More Undecidable Problems

For a given property $P$ of languages, define $L_P$ as the set of all Turing machines (resp. their encodings) that accept languages with $P$, that is

$\qquad \displaystyle L_{p} = \{ ⟨M⟩ \mid \mathcal{L}(M) \text{ has property } P \}$

If $P$ is a trivial property, that is if $P$ holds for all or no language, $L_P$ is decidable, too (as $L_P=\emptyset$ or $L_P = \{\langle M\rangle \mid M \text{ Turing machine }\}$. If $P$ is not trivial, $L_p$ is undecidable (by Rice's theorem), which means the strings in this language (or with such property) cannot be determined if it can be halt.

We determine a language $M$ has property $P$ by reduce $M$ to another $M'$, and check that if $M'$ accepts the reduced string $x$ from the initial string $w$, we can conclude that $L(M)$ and $L(M')$ have property $P$.

However, as the title suggests, we only reduce a single string $w$ to $x$ and if $x$ is accepted, but we conclude the whole $L(M')$ has property $P$. Thus, $M'$ is obviously part of $L_p$. What if some random strings in $L(M')$ do not have property $P$?

What if M accepts some string, but the reduction of those strings are not accepted by M'?

A reduction from language $L$ to language $L’$ is an algorithm (TM that always halts) that takes a string $w$ and converts it to a string $x$, with the property that: $x$ is in $L’$ if and only if $w$ is in $L$.

Does this imply the reduced language $L'$ will contain every property $P$ from $L$? Since we can conclude that if $L'$ is decidable, then $L$ is decidable as well and vice verse. Can we conclude the same thing to property $P$?


texts:
This relates to an answer for this question.
The opinion said that:

Personally, I don’t see much value in coding interviews. The problems I’ve seen asked as coding questions have been (for the most part):

asked by a person who has one specific solution in mind and is unable to recognise an alternative answer or even a better answer (Note: I actually faced this one time - the clown kept telling me I was wrong. For a metaphor of this, see 1 below);

Imagine a coding question to solve traveling salesman in non-polynomial time (a stupid question because it’s not realistic but I’m going for a metaphor here). Imagine, instead, you solved a different NP-complete problem in non-polynomial time and the interviewer wouldn’t accept that solving any one NP-complete problem in non-polynomial time solves them all. If the interviewer lacks the ability to grasp a great answer, then the candidate offering the great answer is filtered out.

I've read in Geeksforgeeks that:

The interesting part is, if any one of the NP complete problems can be solved in polynomial time, then all of them can be solved.

From what I understand, the interviewer gave a TSP problem, to be solved in brute-force approach. The interviewee solved a different problem of the same NP-completeness level in non-polynomial time (maybe using brute-force approach) too. And, literally what I quote from the Geeksforgeeks above.
My questions:

Is it true that if you solve an NP-complete problem in non-polynomial time, the solution also solves other NP-complete problems as well?
Are the solutions (in non-polynomial time) for NP-complete problems universal (one solution can be used for all)?
Why would the interviewee solve another problem instead of the given problem? Or am I misunderstanding something? Is it to show that the approach is universal?

Thank you in advance for your insights.


texts:
Suppose I'm looking for a some unknown number $x$ in the interval $[a,b]$ under the following assumptions:

$x$ is unique.
Given any $t \in [a,b]$ I can check, at some fixed computational cost, whether $t>x$. Let's call this operation $C(t)$.

Let $\epsilon>0$ be some small number. I'm interested in efficient algorithms to find an interval $I$, containing $x$, with length $<\epsilon$. The bisection method begins by using $C((a+b)/2), $ halving $[a,b]$, and repeating the process
 over $\log_2 \left((b-a)/\epsilon \right)$ times. I was wondering if there are more efficient modifications to it, such as breaking the interval into 3 or 4 subintervals at each iteration. Any other efficient alternative is also welcome. Thank you!

P.S. One can assume that $x$ is distributed uniformly in $[a,b]$, and that this process needs to be done many times for different $x$s.


texts: Evaluate in how many ways each cell on a board is under attack by the queens

texts:
There's a board with given dimensions (NxM) and it has few queens places on some of the cells. We need to find in how many ways each cell is under attack by the queens on the board.
e.g.,

....Q
.Q..Q
.....
.....

Each empty cell is denoted by '.' and each cell having a queen placed is represented as 'Q'. For this configuration of board the answer is -

22221
11222
11111
02101

The problem has been stated in InterviewBit Queen Attack.

I solved this problem by listing down all the queens on the board and for each queen I traversed in all eight directions until either I reach the extremes of the board or find another queen while moving in a certain direction and incremented the attack counts for each cell on the way.

This solution didn't run in the expected time. The editorial solution does the counting for each direction for each cell and extends it to neighboring cells in that direction.

What I have not been able to understand is how the editorial solution has better running time that my solution. Can you try to find out for what cases my solution is slower than the editorial solution? Below are the links to the GitHub Gists of my solution and editorial solution -

My Solution
Editorial Solution


texts: The characterization of a problem as PSPACE-complete is ...?

texts:
Let's assume that you found out that some problem $\mathit{\Pi}$ is PSPACE-complete (with respect to your favorite kind of reductions, say, logspace reductions). However, as there are dozens of well-known and very different PSPACE-complete problems, this characterization doesn't tell you much about the real hardness of deciding membership in $\mathit{\Pi}$ (and you determine to refine the hardness of membership in $\mathit{\Pi}$ further by some other means, i.e., different from the good old standard complexity classes).
Now, how do you express in plain English the unsatisfactory fact that the PSPACE-completeness of $\mathit{\Pi}$ doesn't tell you too much? Do you say that the PSPACE-completeness characterization of $\mathit{\Pi}$ is

coarse
coarse-grained
coarsely grained
coarsely granular
crude
gross
grainy
granular
rough
unrefined
... (your choice goes here) ...

?

Which word is idiomatic?


texts:
I wonder about the following decision problem :

Instance: We consider a $n\times p$ matrix $M$ of zeros and ones, and two integers $N$ and $k$.

Question: is it possible to cover all the ones of the matrix with $N$ squares of side length $k$?

It is possible that the squares cover some of the zeros in the matrix, and they can overlap with each other.

I get the impression that it is $\textsf{NP}$-complete (it is clearly $\textsf{NP}$), I find some similarities with Grid covering by rectangles but can't find a good reduction.

Might I get some insight on the problem?

Thanks.

EDIT: After days of reflexion, these are the ideas I've got:

I try to create a reduction from a Satisfiability problem with the following approach.

Given $\varphi = \bigwedge\limits_{i=1}^m C_i$ where $\forall i \in [\![1,m]\!]$, $C_i = (\ell_{i1}\vee \ell_{i2}\vee\ell_{i3})$ and $\ell_{ij}$ is either $x$ or $\neg x$ where $x\in\mathcal{V} = \{x_1,…,x_n\}$. I create the matrix $A$ with dimensions $(2m+2)\times (6n-1)$ defined by:

$\forall j \in [\![1,n]\!], a_{1,6(j-1)+3} = a_{2m+2,6(j-1)+3} = 1$;
$\forall i,j\in [\![1,m]\!]\times [\![1,n]\!]$, for $k = 2i - 1$ and $k = 2i$ and for $p = 6(j-1) +2$, $p = 6(j-1) + 3$ and $p = 6(j-1) + 4$, $a_{kp} = 1$;
all other coefficients are set to 0.

Here's a visual representation of the matrix:

With this matrix, if, for a variable $j$, we allow the use of $2m-1$ squares of size $2\times 2$, we can either cover all of (except extremities) the column $6(j-1)+1$ or the column $6(j-1) + 5$, but not both and not a mix between them. This can simulate a boolean variable!

The idea I got then was to put ones in the column $6(j-1)+1$ save if $x_j$ appears in the clause $C_i$ in which case, $a_{2i-1, 6(j-1)+1}$ and $a_{2i,6(j-1)+1}$ stay to zero (and do the same thing similarly in the column $6(j-1)+5$ with the $\neg x$ litteral).

If we then allow the use of $2n-1$ squares for each clause $C_i$, we need one of the variables to be set correctly in the clause to cover all ones in lines $2i-1$ and $2i$. The problem with this reduction is that you can "gain" some squares in a clause with multiples variables set correctly to change the disposition of a variable elsewhere.

My second idea was to create a reduction from $\texttt{ONE-IN-THREE-SAT}$, in which we ask if there is an assignation to $\varphi$ which satisfies exactly one litteral per clause, or even its restriction where we can suppose that $\varphi$ contains no negations, but I couldn't find something satisfying, so I'd like some help again!


texts: Why number of possible cuts in a graph differ from maximum number of minimum cuts?

texts:
According to this wikipedia link, under the title "Success probability of the contraction algorithm":
Number of possible cuts in a graph is $2^{n-1}-1$, while maximum number of minimum cuts is ${n}\choose{2}$, where $n$ is number of vertices.

My question:
Why number of possible cuts differ from maximum number of minimum cuts? why isn't any cut a candidate minimum cut?


texts:
A 32 – bit wide main memory unit with a capacity of 1 GB is built using 256M X 4-bit DRAM chips. The number of rows of memory cells in the DRAM chip is 2^14. The time taken to perform one refresh operation is 50 nanoseconds. The refresh period is 2 milliseconds. The percentage (rounded to the closet integer) of the time available for performing the memory read/write operations in the main memory unit is _______ .
I calculated that the no of DRAM chips needed is 32. Now each DRAM have rows = 2^14
and columns 2^16 also as we can refresh the rows in parallel and since for one memory cell the time is 50 nanoseconds so for 2^16 columns we will need 2^16 * 50 nano sec ?...Is my approach right
or if i consider that 50 nanoseconds is the time for refresh of a complete row then also it would need a total of 50 nanosec to refresh all in parallel


texts: Problems understanding the Union functionality of the Union-Find Algorithm

texts:
I am currently doing a course based on algorithms (Coursera). I've come across an algorithm called quick find. The course does have reference to Big O Notation. Despite the fact that I do not have much knowledge of Big O, I have been doing some basic reading.

Implementation (Java):

Initializes the array:

public QuickFindUF(int N)
{
    id = new int[N];
    for (int i = 0; i < N; i++)
    id[i] = i;
}

Checks if two input values are connected:

public boolean connected(int p, int q)
{
    return id[p] == id[q];
}

Union Implementation:

public void union(int p, int q)
{
    int pid = id[p];
    int qid = id[q];
    for (int i = 0; i < id.length; i++)
    {
        if (id[i] == pid)
        {
            id[i] = qid;
        }
    }
}

The id variable is a private instance variable.

My Problem:

1) In the study material it says:

  It takes N2 array accesses to process a sequence of N union
  commands on N objects

How can it take N2 if the union method only has a single for loop?

2) It also says that the union method takes

  at most 2N + 2 array accesses

What does this mean? My speculation is that 2N could mean that the array is accessed twice (line 7 and line 9 of the union method). I have no idea what + 2 refers to though.

I apologize if I have incorrectly stated something.

Any help would be highly appreciated. Thank You.


texts: Given a binary heap $H$, indexed in $[1..n]$, whose elements are integers, is there a way to quickly find its median in $O(\log n)$-time?


texts:
Is there a name for the "measure of connectedness", i.e. :
$$\text{MoC} = \frac{d(G)}{|G|-1}$$ with domain of function $D_\text{MoC} = [0,1]$, average degree of graph $d(G)$ and amount of nodes $|G|$? Meaning a quantitive measure for connectedness or meshedness of a graph? E.g. a complete graph would have a MoC of 1, while a graph without edges would have a MoC of 0.


texts: How to prove that minimal DFA is unique?

texts:
My idea is that the number of states in the minimum DFA is equal to the number of equivalent states. So, if there exists another minimum DFA, then it must have different equivalent states than the previous DFA which is not possible.

How do I formally prove this?

EDIT: Maybe something like "since two states are equivalent, they are semantically equivalent and hence, they can't be equivalent and different at the same time" might do if written formally?


texts: Draw lines according to a specific condition

texts:
We have an infinitely planar cartesian coordinate system on which $N$ points are plotted. Cartesian coordinates of the point $i$ are represented by $(X_i,Y_i)$. Now we want to draw $(N−1)$ line segments which may have arbitrary lengths and the points may or may not lie on these lines. The slope of each line must be $1$ or $−1$.

Let's denote the minimum distance we have to walk from a point $i$ to reach a line by $D_i$ and let's say $a=\max(D_1,D_2,D_3,...,D_N)$. We want this distance to be minimum as possible.

Thus we have to plot lines in such a way that it minimizes $a$ and compute $a \sqrt2$.

Devise an optimal procedure to find $a$ and thus compute $a \sqrt2$.

My understanding is as the slopes are $1$ or $-1$ the equations of the lines would be $y = x + c$ or $y = -x + c$ and we just have to find the y-intercept $c$ which minimizes the distance 'a' in the problem. Also, the minimum distance from a point to the line is the length of the perpendicular to the line. So I am having difficulty to devise an algorithm which will check all possible values of $'c'$ and find the optimal one.


texts:
In his 1973 paper On the notion of a random sequence, Levin states (without proving) a characterization of Martin-Löf randomness by writing

  Theorem 3. A sequence $\alpha$ is random w.r.t. the distribution $P$ in the Martin-Löf sense if and only if the probability ratio $P(\alpha_n)/ R(\alpha_n)$ is bounded below

where $R$ is the universal semicomputable (semi)measure.

I feel a bit confused how this ratio could not be bounded below, being the ratio of two positive quantities it should always be bounded below by $0$.


texts: Complement of equality problem of Turing machine is recognisable or not

texts: Complement of equality problem of Turing machines is unrecognisable or not-recognizable but How?. As per my knowledge it is recognisable if you can decide its accept condition but not Reject and opposite is the case with Unrecognisable. But in complement-Eq problem of TM if a string/input accepted by one but not by other you can Accept it, and reject condition will be undecideable so it should be Turin-recognisable


texts: Should two DFAs be complete before making an intersection of them?

texts:
In the slides given by my teacher, the third automaton is the product of the first two:

I tried to do the product myself by doing the transition table of both automata at the same time. I got stuck when I realised that the second automaton has no transition from state $2$ with $a$ as input symbol, thus the automaton should halt at that moment. In the third automaton, I can see there is no transition with input symbol $a$ in any of the states that have $2$ in (sorry for the bad expression, don't know how else to say it).

So when doing the transition table of the two automata, if there is no transition, should I just ignore it like in the 3rd automaton? Or would it be wise to complete the automaton?


texts: Maximum number of states in NFA concluded from the converted DFA

texts:
Assume I have a DFA with 20 states, is it possible to know the maximum number of states of the NFA which it was converted from?

I know that the minimal number of states would be 5 (because you cannot have created a DFA with 20 states from an NFA with 4 states).

But I don't really understand how can I know if there's a maximum that can be determined.


texts: Connected components of the graph on $[n]$ in which $i,j$ are connected if $\mathrm{gcd}(i,j) > g$

texts:
I recently got asked the following question:

A set of $n$ cities are numbered from 1 to $n$. Given a positive integer $g$, two cities are connected if their greatest common divisor is greater than $g$. The number $n$ may be as large as $10^5$.
Alice has a list of $q$ cities that she'd like to visit. Given Alice's list of $q$ origin cities and $q$ destination cities, return a boolean vector with a 1 in the $i$th position indicating that it's possible to reach the $i$th destination city from the $i$th origin city, and 0 if not. The length of the list $q$ may be as large as $10^5$ as well.

I solved this problem with a quadratic time solution. However, the large upper bound for $n$ and $q$ clearly implies there is a better runtime. I haven't yet seen a way to speed up the creation of the graph, however.
My solution builds the graph in quadratic time, using a union find data structure to handle the component merging, and Euclid's algorithm for computing gcd's.
The fundamental question is whether there exists a faster than $O(n^2)$ algorithm to construct and query an undirected graph, when edges are defined by a pairwise rule, and it appears that every pair $(i, j)$ for $1 \leq i,j \leq n$ needs to be looked at.


texts: What is the relationship/difference between best/worse/expected case and big O/omega/theta?

texts:
In the big O section of Cracking the Coding Interview 6th edition, I read the following.

"Best, worse, and expected case describe the big O for expected inputs and scenarios."

"Big O, big omega, big theta describe the upper, lower and tighter bounds for the run-time."

I understand what best, worse,  and the expected case is describing.

I know what bounds are but still don't understand the decoupling of the two concepts. Why would an algorithm have different bounds if the inputs/scenarios are the same?

Thanks in advance!


texts: Is Euler's totient function a primitive recursive function?

texts:
We consider the function $g$ which associates the number of prime integers with $n$ in the set $\{0,...,n\}$. I have to prove that $g$ is a primitive recursive function.

First I defined the set $A=\{i∈\{0,...,n\}:\gcd(i,n)=1\}$. To show that $A$ is a primitive recursive set I said that : $\{0,...,n\}$ is primitive recursive because ${k}$ is primitive recursive by characteristic function and $\{0,...,n\}=\bigcup\limits_{k=0}^{n} \{k\}$ is primitive recursive by the property of $⋃$.

Then the function $\gcd$ is primitive recursive. Indeed we can see that with the function $lcm$. We have $lcm(a,b)=μk≤ab (∃j,l≤ab,aj=k∧bl=k)$
which is a primitive recursive expression. Then by operator division $\gcd$ is a primitive recursive function.

So $A$ is a primitive recursive set.

Now, to prove that $g$ is primitive recursive can I take :

$g(i)=\sum\limits_{i=0}^{n} \chi_{A}(i)$ with $χ_A(i)=1$ if $i∈A$.and $g$ is a finite sum of primitive recursive functions so it is primitive recursive?


texts: Do deterministic context free grammars always have corresponding deterministic push down automata?

texts:
A language $L$ is deterministic context-free if and only if there is a
  deterministic push-down automaton M such that $L = L(M)$.

According to the answer key of this quiz, the above statement is false. Which is odd to me, if a context free language is one that can be defined by a pushdown automata, would a deterministic context free language not also be defined by a deterministic pushdown automata? Perhaps it's the "if and only if" that is at issue here.

I'm also referencing information from this post
Are there inherently ambiguous and deterministic context-free languages?, which does imply that the above statement should be true.


texts: Greater than or equal to operation (32-bit ALU)

texts:
I'm trying to construct a greater than or equal to operation by adding some logic gates or building blocks (i.e. multiplexor and decoder) to my current 32-bit ALU

I'm not quite sure how to do this and nothing on google comes up for this operation from what I could tell.

ALU Design:

Question: How do I add a greater than or equal to operation to the current ALU? Also can you explain the changes you make so I can understand what's going on, thank you!


texts: Can the cache always miss while trying to write to the cache?

texts:
According to the lecture, a virtual address first goes to the TLB.

If the TLB hits, it is then checked, if something has to be either read or written from cache.

In case of writing, it is then checked, if the write access bit is on. If yes, then it is tried to write to the cache.

However now it can happen, that the Cache misses and this attempt is retried indicating that this could continue ad infinitum.

However now I wondered, if there can be really a case for this to happen.


texts: Data structure to determine vertex membership after edge removal from a tree in sub-linear time?

texts:
Consider a tree $T = (V,E)$ and its induced disjoint trees $T_1 = (V_1, E_1), T_2=(V_2, E_2)$ by the removal of an edge $e \in E$.
Is there a data structure that enables the immediate determination of membership of vertex $u \in V$? i.e., is $u\in V_1$?
Ideally a data structure with at most polynomial space complexity.
An example is as follows:
I have a tree that I will remove an edge from it to induce a forest of two tree components. Then, I want to attach another edge to reconnect the components to produce a new tree. This procedure is then repeated M times.  I am looking for a data structure that enables this process to run in O(M) time.


texts: Solving the Path Explosion Problem in Symbolic Execution

texts:
Looking at the Symbolic Execution limitations, there are some good solutions to the "Environment interactions" problems. However, the solutions to the path explosion problem are less than ideal.

  Solutions to the path explosion problem generally use either heuristics for path-finding to increase code coverage,[2] reduce execution time by parallelizing independent paths,[3] or by merging similar paths.[4]

The parallelizing is just adding more power to the situation which doesn't really solve it. The first and third suggestions I am not to familiar with. The first sounds like it has similar problems to testing, in that they are just opting into certain paths based on heuristics, which also doesn't seem to solve it. I am wondering if the solutions to the path explosion problem could be explained here a little bit, either the solutions listed above or anything else. Specifically I am interested in the heuristics one, and what kind of things can be done here.


texts: Can I compute closest split pair of points where distance is strictly less than delta

texts:
I've been studying the closest pair algorithm lately and I found this to be an extremely good and intuitive resource: http://serverbob.3x.ro/IA/DDU0221.html. It is also explained in section 33.4, "Finding the closest pair of points" of introduction to algorithms, third edition  by CLRS.

I understand why I'd need 7 comparisons for a non pairwise distinct set of points and only 5 otherwise (33.4-2). Both of them follow from the fact that I can fit only 4 points, at least Delta away from each other, on a Delta x Delta box.

What I've been wondering though, is if I could trim the number of comparisons down to 3 if I included only points strictly less than Delta away from the middle line, in the middle Delta x 2 Delta strip. The reasoning is that I already have a pair of points Delta away from each other from the recursive calls, I only need points less than Delta and I can only fit 2 points Delta away from each other AND less than Delta from the middle line on each side.

Have I missed something or can I really just compare the 3 following points of every point in a middle strip only containing points strictly less than Delta from the center?

Edit:
I have started a bounty for a very similar question on stack overflow also and we have come up with a very interesting discussion there. So I'm linking it here. We've also started a very insightful chat here.


texts: A push down automaton that recognize exponential strings

texts:
How can I describe a Push Down Automaton that recognize the language $P=\{a^{2^n} | n \geq 0 \}$?

My approach

I know that the language can be described by a Turing Machine, but how i can the stack recognize that language?


texts: Proof the number of expected node in a binary using mathematical induction

texts:
The following algorithm constructs a binary tree.

MakeArray(array[x:y]) (
 if(x==y):
  the root is x
 else:
  pick a number r as root
  MakeArray(array[x:r-1])
  MakeArray(array[r+1:y])
)

Let $a_n$ be the expected number of nodes which have two children in the tree with $n$ nodes generated.
Prove $a_n = \frac{n-2}{n}+\frac{1}{n}\sum_{i=0}^{n-1}(a_{i}+a_{n-i-1})$ using mathematical induction.

I have no idea where to start as I don't even know how to construct a proper equation to carry on the proof. Any help is appreciated.


texts: A 4-bit combinatorial circuit that outputs 1 when integer greater than 7 and is odd number

texts:
I need to draw a combinatorial circuit that when an integer is greater than 7 and is an odd number, the output will be 1. There are 4 inputs representing 4 bits and 1 output wire. The output wire is only 1 if an integer is greater than 7 and is an odd number.

My attempt: If I segment the 4-bit input as r x y z where if the input was 8, the 4-bits would be 1 0 0 1. I know that r and z must have an AND gate but cannot figure out a way to get x y to work. I drew a truth table and found that

1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

must all equal to 1 to satisfy the condition placed.
Any help is appreciated.


texts: Implementing the GSAT algorithm - How to select which literal to flip?

texts:
The GSAT algorithm is, for the most part, straight forward: You get a formula in conjunctive normal form and flip the literals of the clauses until you find a solution that satisfies the formula or you reach the max_tries/max_flips limit and find no solution.

I'm implementing the following algorithm:

procedure GSAT(A,Max_Tries,Max_Flips)
  A: is a CNF formula
  for i:=1 to Max_Tries do
    S <- instantiation of variables
    for j:=1 to Max_Iter do
      if A satisfiable by S then
        return S
      endif
      V <- the variable whose flip yield the most important raise in the number of satisfied clauses;
      S <- S with V flipped;
    endfor
  endfor
  return the best instantiation found
end GSAT

I'm having trouble interpreting the following line:

V <- the variable whose flip yield the most important raise in the number of satisfied clauses;

Isn't the maximum number of satisfied clauses what we're looking for? It seems to me that we're trying to use the solution or approximations to it to find the solution.

I've thought of some ways to do this but It'd be good to hear other points of view (The assumption is that once the variable is flipped once it is selected.):

Generate a state space with all possible flips and search the space for a literal that results in the best approximation to the goal state.
Randomly select the variable that I will flip starting with the literals that are more common.
Pick a random literal.


texts: Deterministic Multi-tape Turing Machine construction

texts:
I'm trying to construct a deterministic multi-tape turing machine for the following language in order to show that $L$ is in $DTIME(n)$:

$$L = \{ www \mid w \in \{a,b\}^+ \}$$

I'm not sure how to get started. Any hints would be appreciated.


texts: First Order Logic, First Order Logic + Recurrence and SQL

texts:
we know that SQL standard is equivalent to First Order Logic (FOL).  I've seen at my lecture that graph connectivity cannot be expressed by FOL, so in SQL as well. But we know that we can easily solve that problem in PTIME. And I've seem the following table:

Query Language   Data Comp.   Expression Comp.
FOL              LOGSPACE     PSPACE
FP               PTIME        EXPTIME

I am not sure what is FP. But, I suppose that it is FIXPOINT. I mean, a first order logic with recursion + fixpoint.

I don't understand that table. I understand the Data Comp. But, I cannot what Expression Comp. means and why Expression Comp. for FP requires so much time.


texts: minimizing the summed cardinality of set unions

texts:
this optimization problem, I am working on, is kind of making me crazy. ;)

Given is a list o of sets (with finite cardinality) of strictly positive integer values (Z>0), e.g.:

o_without_sizes =
[ {1, 2, 3, 4}
, {5, 6}
, {2, 3, 4, 5}
, {5, 6, 7}
, {7, 8}
. {9} ]

Every set has a name n (also in Z>0, but only for identification) and a fixed independent size value s (also in Z>0), e.g.:

type O = [(Name, Size, Values)]
o =
[ (1, 2, {1, 2, 3, 4})
, (2, 1, {5, 6})
, (3, 2, {2, 3, 4, 5})
, (4, 3, {5, 6, 7})
, (5, 2, {7, 8})
. (6, 1, {9}) ]

These sets are to be combined to unions b of a maximum size value sum h (>= max s, that means that no set has a size making it too big to fit into a single union), e.g. 4.

The goal is to find the b so that the sum of cadinalities of the unions in it is as small as possible.
here is a bad b:

size:   3,  cardinality:   6,   sets: [1,2]  ,  values: [1,2,3,4,5,6]
size:   2,  cardinality:   4,   sets: [3]    ,  values: [2,3,4,5]
size:   3,  cardinality:   3,   sets: [4]    ,  values: [5,6,7]
size:   3,  cardinality:   3,   sets: [5,6]  ,  values: [7,8,9]
cardinality sum:  16

and the optimum b for this example:

size:   4,  cardinality:   5,   sets: [3,1]  ,  values: [1,2,3,4,5]
size:   4,  cardinality:   3,   sets: [2,4]  ,  values: [5,6,7]
size:   3,  cardinality:   3,   sets: [5,6]  ,  values: [7,8,9]
cardinality sum:  11

Until now I only implemented a naive brute force solution (Haskell code): http://lpaste.net/7204008959806537728

I was hoping to find a dynamic programming solution like it exists for the (Z>0) 0-1 knapsack problem, but did not yet succeed.
Is my problem perhaps NP-hard? If so, is it many-one-reducible to SAT or something? Or is there a good approximation?

Of course, if there exists a known efficient optimal algorithm, it would be awesome if you could enlighten me. :)


texts: How can I partition a graph such that as few edges as possible cross partition boundaries?

texts:
The following problem appeared while trying to distribute a program over a cluster of computers:

Given an undirected graph $G=(V,E)$ and an integer $n$, partition the vertices of $G$ into $n$ partitions $V_i$ of about equal size such that the number of edges crossing partition boundaries is minimised.

You can imagine $V$ as being chunks of a data set with $E$ indicating which chunks are related to what other chunks. When the computer operates on a chunk $v\in V_i$, it needs to access chunks from all $w\sim_E v$ and the performance is better if as many $w$ as possible are in the same partition $V_i$. The chunks are all of equal size and it is important that each partition $V_i$ contains about the same amount of them.

How can I a) model and b) approximate a good solution for this problem?


texts:
Definition. A word $w \in \Sigma^*$ is primitive if $w=u^n \rightarrow n=1$.

Is it true that a word is primitive if and only if its all cyclic rotations are dstinct?


texts: Cut word from regular language into two parts and swap them. Is the language still regular?

texts:
Define language $L’$ for given regular language $L$ as: $$L’=\{uv | u,v\in\Sigma^{*}, vu\in L\}$$ is language $L’$ also regular?

Hello, I need some help with solving this question.
I need somehow to determine where to divide each word. Or actually - in what state of its automata will that language be. If that makes sense and my understanding of the problem is correct.


texts: Formalization of the shortest path algorithm to a linear program

texts:
I'm trying to understand a formalization of the shortest path algorithm to a linear programming problem:

For a graph $G=(E,V)$, we defined  $F(v)=\{e \in E \mid t(e)=v \}$ and $B(v)=\{ e \in E \mid h(e)=v\}$ where $t(e)$ is a tail of a node, and  $h(e)$ is a head of a node.

Also the solutions for the conditions for the linear problem was defined as $b_v=1$ for every node $v$ except of the root $r$ which from it we find all the shortest paths in the graph where $b_r=-(n-1)$. It is written here "We associate a flow (primal variable) $x_e$ with each arc $e \in E$.

The main linear program is to minimize $\sum\limits_{e\in E }c_ex_e$, subject to $\sum\limits_{e\in B(v)}x_e-\sum\limits_{e\in F(v)}x_e=b_v$ for all $v \in V$ and $x_e \geq 0$ for all $e \in E$, where $c_e$ is the length of arc $e$.

I'd really love your help with understanding what does $x_e$ represent. Is it the number of times I use $e$ in order to find all the shortest paths in the graph?

I don't understand why does the above condition for this linear program is as at it, why does  $\sum\limits_{e\in B(v)}x_e-\sum\limits_{e\in F(v)}x_e=b_v$ for all $v \in V$ should  be $1$ for every node and $-(n-1)$ for the all the root? If I think of a $3$ nodes tree for a graph,for  the middle node we get that the condition equals to $1$, which makes me think that I might be misunderstood what $x_e$ stands for.


texts: Why does Locality Sensitive Hashing use multiple sets of hash tables? How does it guarantee similarity?

texts: With locality sensitive hashing (specifically multi-probe hashing http://www.cs.princeton.edu/cass/papers/mplsh_vldb07.pdf) how are the guarantee of similarity returns made? Why are there multiple tables involved in the hash indexing? Wouldn't that make it LESS probable that an item hashed to a bucket is similar to another rather than the reverse?


texts: Doubt on integrality gap and LP relaxation

texts:
I have an exercise that tells me that, given a problem P (of which now I omit the description) there is no integrality gap between LP and ILP formulation of this problem, and for every fractional LP-solution, there exists an integral
feasible solution with the same cost. Then I have to design a poly-time algorithm that from any
given optimal LP-solution, computes such an optimal integer assignment.

The fact that there is integrality gap what does it mean in this case? I mean, if I design an approximation-algorithm to compute an optimal integer assignment from a given optimal LP-solution, I will get a solution with object value like something  *  Optimal value of LP problem . Isn't this in contrast with the fact that there's no IG? It should mean that the optimal value of LP and ILP should be the same, no?

Please, clarify my doubts.

EDIT:
Michele is very interested in fashion and owns a whole bunch of nice outfits,
collectively forming the set O. A set F of his friends all want to borrow one of Michele’s
outfits to go to a wedding. This should be doable, since |F| ≤ |O|. However, due to different
restrictions like size, body form, or adjustements that have to be made to an outfit to really
look wedding-appropriate, there will be some extra effort w(f, o) ≥ 0 required when any friend
f wants to wear outfit o. Of course, Michele would like to keep the overall effort to a minimum.
a) Model the problem as an integer linear program, and relax this to a corresponding LP.
b) Usually, the optimal solution to a problem’s LP-relaxation is better than that of the original ILP. The factor by which both can differ is called the integrality gap. For Michele’s
problem, there is no such gap and for every fractional LP-solution, there exists an integral
feasible solution with the same cost. Give a polynomial-time algorithm that, from any
given optimal LP-solution, computes such an optimal integer assignmen


texts:
Given code to just an NP-verifier, where the certificate/witness is required to be of size polynomial in the instance, for a language L, can you, from that data alone, construct code for a solver, or generate / get back the language L itself?
At a glance, the answer seems to be yes--you could just try every word, certificate pair; however, there is a part I'm not sure about with this process: sure there are only a finite number of words of each size, but there are an infinte number of words that are poly|w| for any given size |w| that are potential certificates. So, without the certificates, you could be trying different strings as the second input for the same word as first input forever to no avail.
Thanks!


texts:
A. Let $F$ be a monotonically increasing real function from $[0,1]$ onto $[0,1]$. Given an oracle to $F$ and a number $y$, is there a way to calculate the inverse function $F^{-1}(y)$ in a finite number of calls to the oracle?

I think the answer is no, because of a simple counting argument: there are uncountably many possible answers, and with a finite number of calls we can get only countably many answers. Is this correct?

B. Let $F, G$ be two functions as above, and let $H$ be their average: $H(x)=[F(x)+G(x)]/2$. Given an oracle to $F^{-1}$ and an oracle to $G^{-1}$ and a number $y$, is there a way to calculate $H^{-1}(y)$ in a finite number of calls?

I think the answer is no, but how can I formalize the counting argument?

Is this possible to reduce to this problem from problem A? Or from another problem which provably cannot be solved in finite time?

NOTE: It can be argued that any function on reals is inherently infinite because even the output of a real number might take infinite time. So for this question, assume that we have a computer that can input, output and do arithmetics on real numbers in constant time per operation.

similar question was posted in math.SE, no answers yet.


texts: Seeking popular science book on bioinformatics or computational genomics

texts: An intelligent 15-year-old I know is interested in both computer science and genetics.  I told her that these fields make an excellent combination.  I'd like to give her a book on bioinformatics or computational genomics.  I'm looking for a fun book, not a textbook.  Specifically, it should inspire people to want to study the field, not aim to provide in-depth knowledge itself.  I am not interested in books on genetic algorithms.  Any suggestions?


texts: Circle fitting with fixed radius using algorithm by Chernov

texts:
I am doing a project where circle fitting is needed and I came across an algorithm and code found on the website (https://people.cas.uab.edu/~mosya/cl/CPPcircle.html) which works very well.

My question is, can I fix the radius of the circle that is going to be estimated? That means, I have some data that is acquired from a circle and I know the radius of the circle but not position of the center of it. I just need to estimate the center of the circle.

I read the paper by the authors Chernov and Lesort on circle fitting published in 2008 https://arxiv.org/pdf/cs/0301001.pdf and to my understanding, their algorithm incorprates both the center position and the radius into a parameter space and optimize them as a whole. I am wondering is there a way to just optimize the center position (x, y) of a circle whose radius is known?


texts: Are minimum boolean circuit sizes for small problem sizes of an NP-complete problem known?

texts:
I think that a table with the following numeric values would be very interesting, but I could not find any table online displaying them:

Choose any NP-complete problem (say, clique, but a problem having well defined instances of $n$-bit size for every $n$ is probably best for this question). For each value of $n$ (input size), there is a minimum size boolean circuit that solves the problem for instances of size $n$. It is obviously computationally hard to actually compute these minimum sizes, but they can be computed by exhaustive search for small values of $n$.

Is there any table of such values for small $n$ known?


texts:
I'm trying to understand the math behind correcting a radial distortion (caused by a lens), but I'm failing to have it explained in simple terms.

I found several examples that proceed this way: a starting point $P = (x, y)$ is given and it is transformed to another point $P'=(x', y')$ with the following equations

$$\begin{align*}
x' &= x \cdot (1-a \cdot \|P\|) \\
y' &= y \cdot (1-b \cdot \|P\|)\,.
\end{align*}
$$

This causes radial distortion, depending on the constants $a$ and $b$. Here $\|P\|$ is the euclidean norm of the vector from the origin to the point P, i.e. $\|P\|=\sqrt{x^2 + y^2}$.

How can I invert these equations?  In other words, given $x',y'$, I want to get back $x,y$.


texts: Should O(1) necessarily stand for a non-zero constant?

texts: I had a debate with my friend. He argued that $o(1)\subseteq O(1)$, so if a function converges to 0, then it belongs to both $o(1)$ and $O(1)$. However I imagine that $O(1)$ represents a constant time, in essence, a non-zero constant time. Is there a broad acceptance that a function converging to zero belongs to $o(1)$ and not to $O(1)$?


texts: How to calculate an accurate estimated reading time of text?

texts:
I suppose the calculation should not be done by only two factors (average reading speed/words per minute, and word count). But at least by a third parameter, that in my opinion should measure the difficulty of the used vocabulary with some kind of text analysis.

I suppose it would be something like this:

totalWordCount / (avgReadTimePerWord * textDifficulty)

Also I read somewhere that the average reading speed is 120 words per minute. But I have some questions regarding that:

Are people known wich existing algorithms that are capable of doing such accurate calculations considering those factors?
Is the average reading time equal in all languages and if not, how to add language as a factor also? What study shows average reading times per language?
Is it possible to add age as a factor? Or are there known studies on those factors?
If someone has dyslexia. Is their some research that suggest for example they take 30% longer to read? And can we just increase it by 30% in such case or are there other factors in such case?

Goal is to implement this as a function in a programming language like Python or PHP and to use the (personalised) result for creating an output like "this article can be read in approximately 12-14 minutes".

It would be nice if such information is publicly available.


texts: Non-brute force algorithm for a Eulerian like path

texts:
I have a graph with an arbitrary amount of edges and vertexes.  Each vertex having an arbitrary amount of edges connecting to it but in practice the number is usually around 3 or 4 no less than one and no more than a dozen.  I want to find the path that goes to as many vertexes and edges as possible without using any edge more than once.
In addition there are a few special cases that I would like to add but an algorithm that doesn't solve for these is fine:

There are pairs of vertexes that are connected with multiple edges.  I can traverse multiple of these edges but I cannot immediately return to the previous vertex I was at without first going to another vertex.
There are some edges that are one way.
Some vertexes will change the destination of edges connected to themselves depending on the edge you arrived from.  In practice this is always a vertex with two edges that if arrived from one edge will change the other edge to return to the source of the first edge and if arrived from the other edge the first will not change.  In theory it doesn't have to be though.

I know this problem cannot be solved in polynomial time and I have thought of ways to speed up the brute force method I am just wondering if anyone else has any ideas.


texts:
I'm trying to prove that the tenth root of n grows slower than the logarithms but I have no clue.
Also, how can I find which of two functions grows faster? It it related to derivatives?
Thanks a lot.


texts: How many satisfying assignments are there in a set of 3-CNF clauses where no clause share the same variable?

texts:
Say I have a set of 3-CNF clauses
$$\mathcal{S} = \{ x_1 \vee x_2 \vee \bar{x_3}, ~~x_4 \vee x_5 \vee x_6\}$$

where $\bar{x}$ is the negation of $x$. Each variable range over $\mathbb{Z}^2$.

How many satisfying assginments are there for $S$? In general, how many satisfying assignments are there for $S$ is the size of $S$ is k?

This is a question about what is a satisfying assignment for 3-disjunctive clause as much as it is about counting. For example when I just have $C = x_1 \vee x_2 \vee \bar{x_3}$, there are $2^3 = 8$ possible assignments:
$$1 1 1\\
0 1 1 \\
1 0 1\\
1 1 0\\
1 0 0\\
0 1 0\\
0 0 1\\
0 0 0
$$
But which one of these are satisfying assignments?


texts:
Encountered this question but I couldn't solve with the complexity they solved it:

Suppose I have an array that the first and last $\sqrt[\leftroot{-2}\uproot{2}]{n} $ elements has $\frac{n}{5}$ inverted pairs, and the middle $n - 2\sqrt[\leftroot{-2}\uproot{2}]{n}$ elemnts are sorted. What is the complexity of sorting the unsorted array?

They claim in the answer that sorting array with $I$ inversions is $O(n\log{\frac{n}{I}})$.Why?


texts: How to calculate the time complexity of a Catalan-like recurrence by substitution?

texts:
I was given the following problem:

  Calculate the computational time complexity of the recurrence $$P(n) = \begin{cases} 1 & \text{if } n = 1 \\ \sum_{k=1}^{n-1} P(k) P(n-k) & \text{if } n \geq 2 \end{cases}$$ using the substitution method. Answer: $\Omega(2^n)$.

I have seen there is a closed-form for this recurrence but I am unsure whether it can be used out of the blue or not. I don't know if I have to prove it by deriving it from the recurrence or if there are simpler ways of solving such a problem by mere substitution.

On the other hand, I think substitution is not the right tool to use here. I have tried with both reverse and forward substitution, but in neither approach I could determine the function as with other problems (e.g. QuickSort).

Is it possible to solve this problem with only substitution at all? If so, how can I devise it?


texts:
Knapsack problems, Assignment problems can all be expressed as (MILP) mixed integer linear programs. MILP is NP-complete. But Knapsack problem is solvable in pseudo-polynomial time using dynamic programming and 0-1 assignment problem can be solved using Hungarian algorithm in polynomial time. So what makes a MILP problem solvable? Is there any reference?
Thanks


texts: How many recursive calls does it take to compute binomial probability weights?

texts:
I was given an algorithm and I was asked to estimate how often it would be called if I was trying to calculate ${100 \choose 50}0,25^{50}0.75^{50}$, the Binomial distribution of $50$ elements chosen within $100$ elements with $0.25$ their probability to appear.

This is the method:

binomial1(int N, int k, double p) {
    if (N == 0 && k == 0) return 1.0;
    if (N < 0 || k < 0) return 0.0;

    return (1.0 - p) * binomial1(N-1, k, p)
         + p * binomial1(N-1, k-1, p);
}

The question is, how many calls to binomial1 would be required to evaluate binomial1(100, 50, 0.25)?

I tried first the fool strategy to implements a system.out.println within the code with an indice increasing each time the algorithm was called. But I realised that it was something fool when I noticed I reached:

passed 2485266 times

Thus I was wondering that as far that the algorithm is called twice every time it is called, I was wondering if it was simply called $2^{100}$ times? Yet, p*binomial1(N-1, k-1, p) seemed to be called only $50$ times with a parameter $k=50$...

I'm only asking for a hint.


texts: Efficient Algorithm Linear Temporal Logic to Deterministic Rabin Automata

texts:
I am trying to construct an equivalent Deterministic Rabin Automata (DRA) given a Linear Temporal Logic (LTL) Formula. One (expensive) way to do this would be to construct an equivalent Non-deterministic Buchi Automata and then determinize it using Safra's construction.

I am interested to know whether there exist efficient algorithms which can
1. Directly construct DRA from LTL without intermediate NBA construction.
2. Are there any existing tools to do this.

[This is my first question posted here. Kindly point in comment, if I missed any conventions of the forum. Thank you.]


texts: Why are strings immutable in some languages?

texts: String is an immutable class in Java. An immutable class is simply a class whose instances cannot be modified.  Why does the Java programming language choose to make objects of class String immutable?


texts: I am a beginner to predicate logic and BigO and am having though time understanding the definition of BigO in terms of predicate logic in the picture attached. I particularly am unable to understand what is meant by n0 in this context. Any help is greatly appreciated.


texts: When does a type generalise another type?

texts:
In languages like Haskell, with a Hindley-Milner type system, when does a type $t$ generalise a type $u$? I use the definition: $t$ generalises $u$ iff $\forall\ v: v \text{ unifies with } u \rightarrow v \text{ unifies with } t$.

I have an algorithm that given these types returns a unifier if one exist. The unifier is an ordered list of assignments $v_1 \mapsto t_1, v_2 \mapsto t_2, \dots, v_n \mapsto t_n$ such that applying $v_i := t_i$ to both types for ascending $i$ results in two identical types.

For instance, the types $(a,a)$ and $(p,q)$ unify with the unifier $a \mapsto p, p \mapsto q$: after applying these assignments both types are $(q,q)$.

It should be possible to use the unifier to see if a type generalises another type, but I can't figure it out at the moment. I couldn't find an existing algorithm either.

Note: if there is an easier way, without using the unifier, that would be appreciated as well.


texts: Isn't Functional Programming just Imperative Programming in disguise?

texts:
A YouTube video I was watching explained the differences between Imperative and Functional programming by demonstrating how the numbers from 1 to 10 are summed up in Java and in Haskell respectively.

In Java, you must explicitly state each step and assign the result of each step to a variable - something like the following

int total = 0;
     for (int i = 1; i <= 10; i++){
         total = total + i;
     }
return total;

In Haskell, you can simply say:

sum(1..10)

My question is: There obviously is something going on in the background of a Functional language, and that something must be some sort of Imperative process.
It seems like Functional Languages are really just some sort of Imperative-Language APIs.
For example, I can create part of a functional language by defining a method sum(int start, int end) in Java. Did I really create a new type of language right there, or did I just define a set of Imperative method calls that hide imperative instructions from you?

I hope it's clear what I am struggling to understand.


texts: Access a tree by level without traversing

texts:
I need a tree structure that works roughly like the following

for each new child I need to match it (with some criteria) with a parent from the previous level only
when the tree is completely initialized, for each leaf I need to find the first parent ancestor that has siblings, i.e. the node just after the branching point.

While the latter is pretty easy with a tipical tree structure, for the first I'd like to just access all nodes of a layer without traversing the whole tree (even with BFS). Does this have a name?

I'm thinking to just keep track of level number for each node and build a second structure to represent levels.


texts: Poly-time reduction is not antisymmetric

texts:
Lemma. (Transitivity) "$\leq_p$" is a transitive relation on languages, i.e., if $L_1 \leq_p L_2$ and $L_2 \leq_p L_3$, then $L_1 \leq_p L_3$.
Proof. By definition, there are poly-time functions $f$ and $g$ such that $x \in L_1 \Leftrightarrow f(x) \in L_2$ and $y \in L_2 \Leftrightarrow g(y) \in L_3$, thus $x \in L_1 \Leftrightarrow f(x) \in L_2 \Leftrightarrow g(f(x)) \in L_3$. Obviously, $g(f(\cdot))$ is poly-time (since $|f(x)|$ is polynomial in $|x|$).

This lemma proves that "$\leq_p$" is transitive, but how would I prove that it is not antisymmetric?


texts: Algorithm for the complete parenthesization of n factors

texts:
Is there an algorithm that can list all possible parenthesizations of a given set of commutative factors?

This is related to the Catalan number. It, however, merely determines the number of such occurrences, while keeping a given factor order.

As an example (found at the above link): from "abcd", the algorithm should produce { "((ab)c)d", "(a(bc))d", "(ab)(cd)", "a((bc)d)", "a(b(cd))" }.

Another related problem is the optimal matrix multiplication order, where given a number of matrices that ought to be multiplied together, the task is to parenthesize them in an order such as the resulting multiplication operations take the least computational resources. From this, I tried to work out an exhaustive way to list all possibilities, but wasn't able to.

Additionally, if the factors are commutative (thus not matrices in the general case), the number of combinations is larger than the Catalan number. As an example, given the above input, additional elements in the output are expected { "((ab)c)d", "(a(bc))d", "(ab)(cd)", "a((bc)d)", "a(b(cd))", "(ac)(bd)", "d(b(ca))", ... }. In other words, if the factors are commutative, the matrix chain multiplication problem and Catalan number considerations are no longer applicable (at least I can't make a fruitful connection).

So, the question focuses primarily on the algorithm for the general case, i.e. when commutative factors are involved.


texts: Computing Hamming Distance Between Binary Vectors

texts:
Consider the following problem:

Input: We are given a set $S$ of $n$ binary vectors. A binary vector is of the form $(b_0, b_1, ... b_n)$, where $b_i \in \{0, 1\}$. Therefore, there are $n$ vectors of size $n$.

Output: For each vector in $S$, we would like to (efficiently) compute a list of binary vectors from $S$ whose Hamming distance is within some predefined constant $c$.

Output (alternative): Find the pair of vectors with minimum Hamming distance.

Clearly, the above can be done in $O(n^3)$ by computing the Hamming distance pairwise between each vector in S ($\frac{n*(n+1)}{2}$ pairwise combinations and $O(n)$ to compute the Hamming distance). However, I am looking for something more efficient, since $n$ can take large values (say, $n=10^6$).

To speed up the computation, one could use some form of hashing, where we place the binary vectors into $N$ buckets, where every vector in the $i^{th}$ bucket contains exactly $i$ ones. This could work, but in my particular case, one could expect that all binary vectors have approximately the same number of ones, so not much would be gained from such hashing. One could also look to perform some sort of compression on binary vectors and perform Hamming distance computation on the smaller compressed vectors as a bound on the distance, but I suspect there are better approaches.

Another hashing approach would be to subdivide the space into hypercubes and place each vector in one of the cubes. I believe similar approaches are used in physics simulations, where space would be divided in a number of 2D- or 3D-cubes and then compute the interaction of elements within cubes and neighboring cubes.

I have seen variations of the above in many applications, but I am not sure what is the name of the problem or how to efficiently compute the solution. It is worth noting that in my particular case the solutions does not need to be "exact", that is, there can be some errors in the output as long as "most" of it is correct. The main issue seems to be how to avoid computing the distance between vectors that are clearly far apart.

(The structure of the binary vectors in $S$ can be diverse. In some cases, there are few bits set in each vector, while in other cases the vectors can be dense. For the sparse case, the Hamming distance computation can get greatly sped up, but the bottleneck is the $\frac{n*(n+1)}{2}$ comparisons that need to be made.).


texts:
I'm looking for work done on solving some problem which is very similar to the minimum k-union.

The problem:

There's a set of elements $E=\{e_1,e_2,...,e_k\}$ of size $k$, and a family of sets $S_1,S_2,...,S_t$ where each set $S_i$ is contained in $E$: $S_i \subseteq E$.

The objective is to find for each $1 \leq j\leq k$ the "best" subset of $E$ of size $j$, where "best" means that it has the biggest number of sets $S_i$ which are contained in it.
The problem, as well as it being NP-hard, is described here too.

I could use solutions to the minimum k-union to solve this, but that wouldn't be ideal regarding computation time, so hopefully this problem can be reduced to some problem that has approximation algorithms to it.


texts: Counting the number of minimal covers of a binary matrix

texts:
Given a binary $n$-times-$n$ matrix $A$, we'd like to cover the regions comprised of $1$'s with non-intersecting rectangles. A collection of disjoint rectangles that covers all $1$'s (and only $1$'s, i.e., it mustn't cover any $0$'s) is called a cover. (Notice that a problem instance may have many different covers.)

A cover is called a minimum cover if it uses the smallest number of rectnagles possible.

The counting problem I'm interested in is: given an $n$-times-$n$ binary matrix $A$, count the number of minimum covers of $A$.

What can you say about this problem? (This post was inspired by this SO question.)


texts: PCP variant in P with non 0 randomness and polynomial proof

texts: I am trying to show that a particular language $L$ in PCP(log,q) is also in P. The PCP protocol works as follows: log many random bits and  checks at q positions in a polynomial length proof. The protocol accepts if two or more queries are 1. Assume that this has perfect completeness.  I think one can handle randomness in P by usual methods. I am having problem with using the bound on queries to show that it is in P. How to show that $L$ can be recognized by a polytime algorithm? Can we somehow use maxSAT equivalent form for PCP?


texts: Algorithm for units allotment to the customers based on preferences

texts:
I'm searching for a simple algorithm to allotment a real estate unit for the customer based on the customer preferences like the following table.

Each customer has a priorities and we should allocate a unit for each customer, what is the name of this algorithms type to cover all scenarios.


texts: Name for Turning DAG into redundant tree

texts:
I am looking for a term:

How is the tree called that you can obtain from a DAG by going top-down and appending all visited nodes to a tree, thereby copying nodes from the DAG into multiple occurences in the tree?

The resulting tree will contain all edges and nodes from the original DAG and a number of nodes multiple times.

A -> B
|    |
v    v
C -> D

Will be turned into:

A -> B -> D
|
v
C
|
v
D

If you need clarifications, please ask.


texts: What happens at the decode phase of the instruction cycle?

texts:
I am reading about the various phases of the Instruction Execution, I found out that we have three phases like below.

Fectch
Decode
Execute

Now if the part I don't understand is why do we need a decode phase ? The instruction will already be stored in a binary format at some memory location, why not just fetch and execute it.


texts: Suitability of high-level languages for embedded systems

texts: Low-level languages have for a long time dominated the field of embedded systems due to their rapidity and flexibility. As high level languages are becoming faster and faster, might the situation get reversed soon? Can high-level languages become frequent in embedded systems in a near (or not so near) future? What would it take for a high-level language to be suitable for embedded systems?


texts: For multi-tape Turing machines, can we assume that each tape can be in its own state independently of the other tapes?

texts:
When we consider multi-tape Turing machines, we can assume that each tape is accessed with a separate head and each head can move independently of the other heads. But can we assume that each tape can be in its own state independently of the other tapes (for example, tape 1 in state A, tape 2 in state F, tape 3 in state X simultaneously)?

Then, for example, the table of instructions for some three-tape two-symbol ("0" and "1") machine can look like this:

    | 000         | 001         | ...
----------------------------------
AAA | 011/BXZ/LRL | 010/XYB/RRR | ...
----------------------------------
AAB | 001/TSH/LLR | 110/AET/LLL | ...
----------------------------------
...

where the first cell of the table can be interpreted as follows: if the first tape is in state A, the first head is over the cell with symbol 0, the second tape is in state A, the second head is over the cell with symbol 0, the third tape is in state A, the third head is over the cell with symbol 0, then the first head writes "0" instead of "0", then the first tape goes into state B, then the first head moves to the left, then the second head writes "1" instead of "0", then the second tape goes into state X, then the second head moves to the right, then the third head writes "1" instead of "0", then the third tape goes into state Z, then the third head moves to the left.


texts:
Lets assume $P = NP$. Can we say if every language $L \in P$, then $L \in NPC$?

I read $P \subseteq NP$, which means that $L\in NP$. So I know for example, that a language can be $NP \text{ hard}$, but it doesn't have to be in $NP$, e.g. $HALT$.

But what about the case above. Is the language also $NPC$?


texts: Number of unique prefixes in canonical huffman tree

texts:
I am trying to implement decompression algorithm based on huffman trees. I am trying to validate my assumptions.

Assume that you have alphabet of 350 symbols. Maximum encoded code length is 15 bits. How many different combinations of first 9 bits of each code longer than 9 bits can be encoded in this tree ?

I am only interested in these first 9 bits of codes which have length > 9 bits, since they determine memory requirement of the algorithm..

Tree is ordered by bit length, so that shorter codes lexicographically precede longer ones.

By my thinking there are 2 edge cases:

Each code has same length: whole tree can be encoded on $log2(350) \approx 8.5 < 9$ bits and i don't need to worry about codes with length > 9, since there aren't any.
Tree is maximally right-heavy, as many code as possible have length of 15 bits. Last 6 bits can encode $2^6 = 64$ symbols, since we need to encode 350 symbols, we can get the factor of 6 to cover all symbols by extending maximally branching tree upwards 3 bits. In this case codes which have maximum bit length share 6 bit prefix, have 3 bits different and then have 6 bit suffix that is irrelevant at this point.

Thanks to the ordering constraint, codes with similar lexicographic value and similar lengths will be grouped (will share same region of the tree, therefore same prefix)

In other cases, there is no way to create tree(provided maximum code length, number of encoded symbols and ordering of the code is satisfied) that would require more space.

If I assume most codes have bit length of let's say 11, that means I need to store $$2^{11-9=2} = 4 $$ codes for each prefix. In order to encode 350 symbols, I would extend the branching upwards 7 bits, creating at most 128 unique blocks(each block groups codes with same 9 bit prefix) , and I would need to store $128*4=512$ additional codes.

And since tree is ordered, longest codes will always be on the "right" and will be lexicographically grouped.

By these assumptions I came to the conclusion that I need to be able to store $512 + (8 * 64) = 1024$ codes. first 9 bits can be stored directly, and if code has length > 9, there is maximum  of 8 different 9-bit prefixes, and for each unique prefix I need to store $2^6=64$ available combinations for 6 bit suffix.

Seems about right, but I would still like for someone to prove me wrong if I am.


texts: Must a function in lambda-calculus which inputs a boolean function be defined in a certian way?

texts:
This question is my best attempt to get at a more general question about what one can get from terms in the lambda calculus.

Using the church encoding, we define booleans by
$\texttt{true} = \lambda x,y.x$ and $\texttt{false} = \lambda x,y.y$

Define the set of terms $Bool = \{\texttt{true}, \texttt{false}\}$, and
let $Bool \to Bool = \{g \; | \; \text{if } b \in Bool \text{ then } g \; b \in Bool\}$

Let $f$ be a term with the property that if $g \in Bool \to Bool$ then $f \; g$ normalizes to a boolean.

Intuitively, I believe $f$ can be either a constant function or it can use $g$. Precisely:
Is it true that any such f satisfies one of the following properties:

There exists some term $b \in Bool$ so that for any $g \in Bool \to Bool$, $f \; g = b $
There exists some term $b \in Bool$ so that for any $g \in Bool \to Bool$, $f \; g = g \; b $
There exists some term $b \in Bool$ so that for any $g \in Bool \to Bool$, $f \; g = not (g \; b) $
EDIT: as Derik points out, the above three cases only capture 6 of the 16 set-theoretic functions of type (Bool -> Bool) -> Bool. The point was can $f$ be defined in a way other than those set theoretic ones.

(where $a = b$ means that $a$ normalizes to $b$)


texts: For any non-trivial $A,B$, finding a language which both are polynomially reducible to

texts:
Given two non-trivial (not $\emptyset$ or $\Sigma^*$) languages $A$, $B$ over an alphabet $\Sigma$, which of the following is correct:
a. There is a language $C$ such that $A\leq_pC$ and $B\leq_pC$.
[..]
c. There is a language $C$ such that $C\leq_pA$ and $C\leq_pB$.

According to two different sources I've seen the correct answer seems to be (a), which is exactly why I'm trying to understand two things:

Why is (a) a correct answer? Taking two languages in $EXP$, for example, I do not see why it's obvious they are polynomially reducible to each other.

Why is (c) not a correct answer? Taking a language $C\in P$ since $A$ and $B$ are not trivial there are some $a\in A, a'\notin A$ and $b\in B, b'\notin B$, and therefore given a polynomial TM $M$ deciding $C$ I can define a reduction $f$ to $A$ by $f(x)=a$ if  $M(x)$ accepts and $f(x)=a'$ otherwise and similarly for $B$, so it seems to me that (c) is a correct answer.


texts: 3-SAT and Systems of Nonlinear Modular Equations

texts:
How is the 3-SAT problem reduced to solving for a system of nonlinear modular equations?

I have read  https://stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete in how to prove that a problem is NP complete?.  But how is this done for systems of nonlinear modular equations specifically?

In that question above, Albert S. lays out nice steps:

"In order to prove that a problem $L$ is NP-complete, we need to do the following steps:

Prove your problem $L$ belongs to NP (that is that given a solution you can verify it in polynomial time)
Select a known NP-complete problem $L'$
Describe an algorithm $f$ that transforms $L'$ into $L$
Prove that your algorithm is correct (formally: $x ∈ L'$ if and only if $f(x) ∈ L$ )
Prove that also $f$ runs in polynomial time"

In other words

1) Where can one find (in the literature or elsewhere) the algorithm $f$ that reduced SAT to the problem of solving a system of nonlinear modular equations originally, so that he or she can better learn about the time complexity of nonlinear modular equations or 2) Could anyone answer below how it is reduced?

Does SAT reduce to solving a system of problem q?

Problem q

Given the coefficients $a$, are there any integer solutions for $x$?  List them:$$a_n x^n + \dots + a_1 x + a_0 = 0 \pmod m$$


texts: What's the fastest time complexity algorithm for finding maximal paths in an unweighted directed graph?

texts:
I see a lot of interest online to the problems of finding shortest paths, longest paths, and all simple paths. I'm interested in implementing a state-of-the-art algorithm to find all (simple) maximal paths of an directed graph without weights for an open-source package.
It may be useful for me to quickly demarcate some related concepts. By maximal path, I mean a path that cannot be made longer by prepending or appending vertices to it. The maximum paths are the longest paths among the maximal paths, but I am not asking about this subset. The longest paths between two vertices are the maximal paths between two vertices, and while they have an intersection with the maximal paths they are not identical concepts.
A naive approach would be to generate all simple paths and test the criterion. Another approach would be to find all longest paths between pairs of nodes, and then filter down. I am hopeful that there is a more efficient approach.
What algorithm would efficiently generate all the simple maximal paths of an unweighted directed graph?


texts: Python: Clustering based on pairwise distance matrix

texts:
I have a matrix which represents the distances between every two relevant items. For example, M[i][j] holds the distance between items i and j. My next aim is to cluster items by these distances.
I can provide some parameters: maximal number of clusters, maximal distance between two items in a cluster and minimal number of items in a cluster.
I cannot, however, provide the "central items" which the algorithm should start with.
I went through some of python's clustering packages, like scikit-learn, but did not find anything that matches.

Any ideas?

Thank you :)


texts: What is the definition of computable partial function?

texts: Let $f:\mathbb{N} \to \mathbb{N}$ be a computable partial functions and $T$ a Turing Machine which computes it. By this I understand that $T$ writes $f(n)$ on its tape and halts when $n$ is an input on which $f$ is defined. But then what should $T$ do on inputs from $\mathbb{N}$ for which $f$ is undefined, and what should it do on inputs that do not represent a natural number? Should it halt or not?