texts: Time complexity for concatenating strings

texts:
I was going through this piece of code from an algorithms books and something doesn't look clear

Please ignore the spelling errors,

How does 0(x + 2x + nx) reduce to o(xn^2) ?

My analogy, assuming x is a constant 1 and n is 2
(x + 2x) == 3 assuming x is a constant 1

From the book
(x2^2) == 4 assuming x is a constant 1

Am i right ?


texts: Definition of the cyclic shift of a formal language?

texts:
Wikipedia says, the context-free languages are closed under

  the cyclic shift of $L$ (the language $\{vu : uv \in L \}$)

So I am looking for the definition of the cyclic shift operation on formal languages.

From the quote, what are required on $u$ and $v$? Are they in $L$, or in $alphabet(L)^*$? Thanks.


texts: Expressing conditional in linear program

texts:
I have two variables $A$ and $B$, with $A$ being binary and $B$ is a real number where $B \ge 0$. My conditions are:

if B > 0
         A = 1
else
         A = 0

How to express this as a linear program? I have figured out one condition using the big-M method:

$MA \gt B$

which means that if $B>0$, then $A$ must be 1 to satisfy this constraint. However if $B=0$, then $A$ can be either 1 or 0, and I need another constraint. How to enforce $A$ to be 0 when $B=0$?


texts:
To choose 3 items out of 5 items [1, 2, 3, 4, 5], Donald Knuth's lexicographic algorithm (The Art of Computer Programming, Vol 4A, 2011, p. 358, Algorithm L (lexicographic combinations)) gives:

[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 5], [1, 3, 5], [2, 3, 5], [1, 4, 5], [2, 4, 5], [3, 4, 5]]

or, if strictly following the algorithm, each combination is reversed, making it:

[[3, 2, 1], [4, 2, 1], [4, 3, 1], [4, 3, 2], [5, 2, 1], [5, 3, 1], [5, 3, 2], [5, 4, 1], [5, 4, 2], [5, 4, 3]]

while Combinatorial Algorithms by Nijenhuis and Wilf, 2nd Ed, 1978, p. 26 cited "alphabetic order" or "lexicographic order" of:

[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], ...

so they are different.  Which is actually lexicographic order, or are all of them lexicographic order, and why?


texts: Drawing a DFA for a language/regular expression

texts:
how would you draw a DFA for the language over {a,b,c} of all words where every occurrence of b is preceded and followed by a.

My thinking of this is that the regular expression for this is a* c* (aba)* a* c* although I am not too sure. Any help would be appreciated thanks


texts: Best route around confirmed appts - Traveling Salesman Problem

texts:
First, I am not a programmer, but an end user.  We are trying to come up with a solution to a TSP issue that is causing us SIGNIFICANT time being wasted "manually" routing.

Here is the issue.  We receive customers to go see.

We route, place on the calendar and confirm about 50% of the appointments before more customers come in that need to be added into the route, placed on the calendar and called to confirm.

We are having a hard time automating the routing process after part of the customers are confirmed and new ones come in.  We currently manually create the route which takes a lot of wasted time.

Any suggestions?  Keep in mind, that I am not a programmer but the end user who is desperate to get a solution.

Thank you!


texts: Expected behavior in the min max random assignment problem

texts:
Consider the standard assignment problem: $n$ people are assigned to n jobs (one person to one job) so to minimize the sum of costs. When the costs are generated randomly (using the exponential (1) distribution), it is known that the expected sum of costs is $\pi^2/6$.
An alternative solution to the assignment problem is to choose an allocation that instead minimizes the largest cost incurred by any individual, in the spirit of the John Rawls fairness criteria. Is it known what is the random sum of costs in the random version of the problem?


texts: Arden's lemma applicability on context free grammars

texts:
The Arden's lemma states that there exists a solution to the equation between regular expressions
r = sr + t, with r unknown, and it is s*t.

I went through some other topics on the forum and I always saw it being applied, for example, on grammars that have productions like

S->AS|b

so that L(S) = L(A)L(S) + b and the solution is L(A)*b.

However, on some student notes from a classmate I found this example:

S->ASA|A

A->aAa|Ab|e

and the Arden's rule is applied in this way without any further manipulation of the grammar:

L(S) = L(A)L(S)L(A) + L(A) and it concludes by saying that L(S) = L(A)*

This seems wrong to me, but I want to check first whether there is some further hypothesis that can be applied here to make the statement valid.
For example, I wonder if it is decidable (and of course valid) whether the productions S->ASA|A generate the same language of the productions S->AAS|A.

Can somebody please help me?


texts: Smallest chain length in a Range Collatz Conjecture

texts:
I'm trying to see if I can find an algorithm such that given a range [m,n], I want to output the number such that on application of either of these steps, I can reduce the number to 1 in the minimal steps.

If odd, multiply by 3 and add 1.
If even, divide by 2.

m,n are small enough to ensure the collatz conjecture holds as the problem is directly related to it.

Now I realised that if any power of 2 lies between m and n, inclusive, that is directly the answer and that can be checked easily.

However, I couldn't find anything on the net if there was an optimal way to see if a range doesn't include a power of 2, what can be done. The brute force is way too long for this as the number of steps per number really varies and I feel this would take very long. I was wondering if there was some optimisation to this.


texts: Prove finding a near clique is NP-complete

texts: An undirected graph is a near clique if adding an additional edge would make it a clique. Formally, a graph $G = (V,E)$ contains a near clique of size $k$ where $k$ is a positive integer in $G$ if there exists $S \subseteq V$ where $|S| = k$ and $u,v \in S$ where $(u,v) \not\in E$, and $S$ forms a clique in $(V,E \cup \{(u,v)\})$. How can I show finding a near clique of size $k$ in $G$ is NP-complete?


texts: Generic tree with minimum weighted path length problem

texts:
Suppose there are an undirected graph $G = (V, E)$ and a function $f : V \rightarrow \mathbb{R}$, which associates a weight for each vertex in $G$. I was wondering if it is possible to find a tree $T = (V, E_T)$, where $E_T \subseteq E$ and $\sum_{i \in V} f(i) d_{i}^T$ is minimal. The root of all trees must be a predetermined node $u \in V$ and $d_i^T$ returns the depth of a node $i$ in the tree $T$.

It looks like a tree with minimum weighted path length problem, which could be built using a Huffman tree, but as it turns out Huffman tree is supposed to be binary, but I would like to find a generic tree, whose the degree of the nodes may be more than two.

Has this problem been classified regarding its complexity?


texts: Is applying a formula a kind of reasoning?

texts:
Supposed I have a set of simple rules, e.g.

if A is between 10 and 20 and B is between 3 and 5, then use 3

and this rules are used in some kind of (more or less) mathematical formula (for example, A + B = C), would you count this as a form of reasoning or inference of a knowledge based system?

You have a knowledge base (the rules) and you get a result (a decision) by applying this rules in a specific way.

I'm curious about your opinions.
Thanks!


texts: Will this address result in a cache hit or miss for these cache mapping functions?

texts:
The Problem:  A CPU produces the following sequence of read addresses in hex.
   Suppose the cache is empty to begin with and assuming an LRU replacement, determine whether each address produces a hit or miss for a) direct mapped cache b) fully associative cache c) two way set associative cache.

20 0010 0000
04 0000 0100
28 0010 1000
60 0110 0000
20 0010 0000

Here is the table of my work thus far (ones I highlighted are ones I am unsure about)

I know that because the cache is empty to begin with, the first five read addresses will produce produces because the addresses are not already in the cache.

I'am having trouble with the last address. The last address is a repeat of the first address. I know that in fully associative deals with the collision problem by allowing a memory location to go into any cache line so the first won't get overwritten and a hit will be produced.

For directly mapped, how can you tell if the first address has been overwritten or not? I know that LRU replacement is being used so if there was a collision, the first address would get overwritten. But I am not sure if there would be collision within the first five addresses(you don't have access to the number of cache lines.

For two set associative, how would you identify which sets each address belongs to? There could be different interpretations. Like you could see, reading from left to right, bits 4-5 match in addresses starting with 20, 28, 60 so 20 would get overwritten, producing a miss. At the same time, a different interpretation could lead to the conclusion that the first doesn't get replaced.


texts: Subsymbolic/multimedia knowledge - query, creation and reasoning? Reference request?

texts:
One can consider multimedia data as a matrix of pixels, but, of course - multimedia data contains higher-order knowledge as well. E.g. everyone can describe famous paintings in terms of colours, shapes, temper, artistic techniques and so on, only rarey one describes the painting as a matrix of pixels. So - are there scientific efforts to capture, query, create, use and generate this higher-order knowledge from multimedia data in general form?

I am aware of the different specialised efforts, like pattern recognition, feature extraction from the pictures, trend extraction from the time-series (sounds), but are there efforts of unified handling of this sort of knowledge?

There is computational creativity field with strong links to aesthetics (e.g. efforts to classify what computer artwork is or is not an art) and such general framework for subsymbolic knowledge would be very desirable addition to computational creativity.

There is universal logic research efforts in the field of symbolic knowledge, so, maybe such universal approach exist for subsymbolic knowledge as well?


texts: What is the name of this function of a tree?

texts:
I've written a recursive function of a tree, and I would like to know what it's called!  It's not quite the same as the height or the width of a tree, but it seems kind of like a width.

Assuming the tree $T$ is binary, we can define the function $f(T)$ as follows.  If $T$ has a only a single node, let $f(T) = 1$.  Otherwise, let $T_0$ and $T_1$ be the two trees rooted at the child nodes $T$'s root.  If $f(T_0) = f(T_1)$, then let $F(T) = F(T_0) + 1$; otherwise, let $f(T) = \max(f(T_0), f(T_1))$.

The function $f$ is generalized as follows to trees that are not necessarily binary.  As before, let $f(T) = 1$ when $T$ has no edges.  Otherwise, let $T_0, \dots, T_k$ be the $k+1$ subtrees rooted at the child nodes of $T$'s root, sorted by descending values of $f$.  Then let $f(T) = \max_i(f(T_i) + i)$.


texts:
I've got a confusion in the following section of a book. Here we taking about FCFS Scheduling. I feel that calculation table is incorrect in the book. Because P3 got completed at time 7, it's turnaround time should be 7-3 because third process arrival time is 3 so why they take 1? Remember turn around time = t(process completed)-t(process submitted)

For P4 it's 11-4 which I feel wrong again. Further for P5. So I want to know whether I'm wrong in understanding this all or the following is really a wrong calculation. Can someone please explain. Thanks!
Check the fallowing links for book scan:
http://i.stack.imgur.com/oGtva.jpg
http://i.stack.imgur.com/mVP03.jpg


texts: Number of parenthesizations and Catalan numbers

texts:
I read in CLRS that the number of possible parenthesizations for a product of $n$ matrices is given by the recursive formula:

$$
    P(n)=
\begin{cases}
    1 & \text{if } n = 1,\\
    \sum^{n-1}_{k=1} P(k)P(n-k)              & \text{if } n \ge2.
\end{cases}
$$

This comes from the following two facts:

For $n=1$ there is only only item, so only one way to fully parenthesize a matrix product.
For $n\geq2$ a fully parenthesized matrix product is the product of two fully parenthesized subproducts, and the split between the two subproducts may occur between the $k$th and $(k+1)$st matrices for any $k=1,2,\ldots, n-1$.

So far so good.

Now, I know that $\sum^{n-1}_{k=1} P(k)P(n-k)$ has a strong relationship with Catalan numbers, and I'm hoping to establish that relationship with precision.

For background, Catalan numbers are defined as a sequence of the following form:

$${\displaystyle C_{0}=1\quad {\text{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{for }}n\geq 0,}$$

where a term in the sequence is also known to follow the alternative expression: $C_n={\tfrac {1}{n+1}}{\tbinom {2n}{n}}.$

Expressing the original recurrence in terms of Catalan numbers shouldn't be hard, but the differences in summation and sequence indices are making it difficult for me. What's a good way to rearrange these types of Eqs. to re-express e.g. the first Eq. as a function of the second one?


texts: Any good source explaining multiprocessor synchronization techniques and their implementation

texts:
I need to study how synchronization is done in a multiprocessor operating system, but I am unable to find a good source. I have read about it in the book "Modern Operating System" by Tanenbaum, but I need to study the actual implementation in more detail.
Any good book/paper or online blog post will do.


texts: Is every language described by a grammar?

texts:
I read the following argument showing that not every language is described by a grammar:

For a fixed alphabet $\Sigma$ and variables $V$ there are uncountable many languages over $\Sigma$ since the power set of $\Sigma^\ast$ is uncountable. But grammars are finite objects by construction and thus there are only countably many grammars. In total, there can only be countably many languages described by grammars. Hence, there are this uncountably many languages that cannot be described by grammars.

I understand the idea of the argument, however i am not convinced by how they show that there are only countably many grammars. What do they mean by "finite objects"? Couldn't one just take the set $\{ (V,\Sigma, P, S) | \; P\subseteq (V\cup \Sigma)^+ \times (V\cup \Sigma)^\ast,\; S\in V\}$, which is clearly uncountable, to get uncountably many grammars? Or do the languages that they generate fall together so often that we only get countably many languages generated by grammars in the end?


texts:
Please forgive me for asking a novice question, but I'm a beginner at algorithms and complexities, and it's sometimes hard to understand how the complexity for a specific algorithm has come about.

I was reading the DFS algorithm from Introduction to Algorithms by Cormen, and this was the algorithm:

G        -> graph
G.V      -> set of vertices in G
u.π      -> parent vertex of vertex u
G.Adj[u] -> adjacency list of vertex u

DFS(G)
1   for each vertex u ∈ G.V
2       u.color = WHITE
3       u.π = NIL
4   time = 0
5   for each vertex u ∈ G.V
6       if u.color == WHITE
7         DFS-VISIT(G,u)

DFS-VISIT(G,u)
1   time = time + 1            // white vertex u has just been discovered
2   u.d = time
3   u.color = GRAY
4   for each v ∈ G.Adj[u]      // explore edge u
5       if v.color == WHITE
6           v.π = u
7           DFS-VISIT(G,v)
8   u.color = BLACK            // blacken u; it is finished
9   time = time + 1
10  u.f = time

It then said lines 1-3 and 5-7 are O(V), exclusive of the time to execute the calls to DFS-VISIT().
In DFS-VISIT(), lines 4-7 are O(E), because the sum of the adjacency lists of all the vertices is the number of edges. And then it concluded that the total complexity of DFS() is O(V + E).

I don't understand how that came about. DFS-VISIT() is called inside DFS(). So, if lines 5-7 of DFS() are O(V) and DFS-VISIT() is O(E), then shouldn't the total time complexity of DFS() be O(VE)?


texts: Defining a Turing machine for $0^n 1^n 0^1$

texts:
I am new to understanding Turing machines and I am trying to define a Turing machine that for the language $L = 0^{n}1^{n}0^{n}$.

I am not quite sure how to give an implementation level description of Turing machine that decides L. This is what I have tried

Define Turing machine M = On input string w
1. Scan the input from left to right to make sure that
   it is a member of 0∗1∗0∗ and reject if it isn't.
2. Return tape head to left-hand end of tape.
3. Repeat the following until no more 0s left on tape.
4. Replace the leftmost 0 with x.
5. Scan right until a 1 occurs. If there are no 1s, reject.
6. Replace the leftmost 1 with x.
7. Scan right until a 0 occurs. If there are no 0s, reject.
8. Replace the leftmost 0 with x.
9. Return tape head to left-hand end of tape, and go to stage 3.
10. If the tape contains any 1s or 0s in that order, reject. Otherwise, accept.

In this case I am treating the $0^n$ at the very end as a completely new symbol. I am not sure if this is the right approach? I think I understand how to handle up to $L = 0^n1^n$ but not $0^n$ again at the end. Any help to put me in the right direction would be appreciated.


texts: Given the "programs as proofs" isomorphism, how do we know that the program isn't lying?

texts:
I've been studying constructive type theory (CTT) and one of the things that I'm not clear on is  the proof part: Proving the correctness of a program in a form of a proof that's nothing but the program itself (Curry-Howard Correspondence)

Most examples that I've seen in books (e.g., Type Theory and Functional Programming - Thomson and TaPL) show the "proofs" on $\lambda$-abstractions and applications on terms (i.e., literally $a, b, e...$). The proofs seem to mostly rely on the type signatures of the functions, under the assumption that the function does what it claims. Not much is discussed about the "how" of the function's correctness.

For example, when writing a real program (e.g., in Haskell and other [pure] functional languages), the function under consideration could do any arbitrary computation and return a term of the correct type for the proof to go through (statically speaking). So how do we know that the program is computationally doing the "right" thing (dynamically speaking) and not just faking it to get past a proofing system?

From what I understand, here's how things should go (and probably are, but I'm not sure if I'm right), crudely speaking:

Given a program's specification in something like predicate logic we "convert" it into an equivalent "typed representation"
Using backward inference we substitute the "functions" with their appropriate values, which themselves could be other functions (i.e., we replace the functions with their computation rules, but I'm thinking more on the lines of replacing the function with its body, from a programming point of view, for the sake of argument. Assuming that they're "returning" the correct type this seems like a believable substitution)
We continue doing #2 above till we hit primitive operations (again, crudely speaking) which we can trivially prove (or if not, maybe the proof is "simple" enough).
Once we've hit all the "axioms" (or trivial proofs) along all the branches of backward inferences, we stop.
QED

Two questions:

Is my understanding/intuition of "how" the proof of correctness works in CTT works correct? It looks like it won't be possible for the program to "cheat" this or can it?
And secondly, is this what proof assistants like Coq help you prove/analyze (at a high level)?


texts: Halting problem for turing machines with one input

texts:
My question is:

Is there a simple construction similar to Turing's 'liar' program that shows that Turing machines plus a halting oracle cannot decide if a given Turing machine halts on all inputs.

When I talk about the liar program I am referring to the standard proof that a Turing machine can't determine the halting of all other Turing machines, since case analysis on the following leads to contradictions
def Liar(T):
   if Halts('T(T)'):
      loop()
   else:
      return

I can see that having a Halting oracle would allow me to determine if a Turing machine halts on any finite set of inputs (We would just run it all in order).
If we call regular Turing machines level 0, we can call Turing machines plus the halting oracle level 1. I have seen that the proof using the Liar program works just the same to show that level 1 machines have their own Halting problem which is undecidable for them.


texts: Given the set of length of triangle, find the Maximum Area Triangle

texts:
Suppose we are given an array of numbers representing lengths of line segments.  Find which three of these segments can be assembled into a triangle with maximum area.

I can compute the areas of all $O(n^3)$ possible triangles in $O(n^3)$ time using Heron's formula, and then return the largest. Can this be improved to $O(n^2)$ time? Or even faster?


texts:
Here is the problem:

There are connected graph with nodes representing a number of people. Each node/person has an opinion on a topic e.g. trump vs clinton, paper books vs kindle, etc

The goal is make every node in a graph share the same opinion, by selecting a specific subset of nodes, in a particular sequence.

If majority of a person A's friends support trump, but person A supports clinton. if person A is selected, his/her opinion will change to trump.

If person's friends opinions are equally divided, then you can decided the selected person's opinion.

I am running out of ideas as how to proof this is achievable. Maybe some of you can give me some pointers.


texts: How do the following Hash Functions compare?

texts:
Consider the two hash functions used to map IP addresses. $x_i$ represents a octave (or "bit field") of the address.

Hash Function 1:
$$h_a(x_1, x_2, x_3, x_4) = \sum^{4}_{i=1} a_ix_i \bmod n$$

Where $n$ is a prime number closest to the total number of IP addresses being mapped. The probability of two IP addresses being mapped to the same bucket is $\frac{1}{n}$ using this hash function.

Hash Function 2:

$$h_a(x_1, x_2, x_3, x_4) = \sum^{4}_{i=1} x_i \bmod n$$

What would the probability to two IP addresses being mapped to the same bucket be using the second hashing function?


texts: Efficiently find the next item in a sequence to exceed some bounds

texts:
I have a bounded sequence of integers, and for each element, I want to know if the sequence next goes some distance above that element, below that element, or neither.  This is straightforward in quadratic time; is there a more efficient solution?

More formally, I have $N$ integers $a_i \in [0, R)$, upper and lower offsets $U, L \in [0, R)$, and a window $W < N$.  For each $i$, define:

$$
f(i) = \min\left\{j \in (i, i + W] \mid x_{j} < x_{i} - L \lor x_{j} > x_{i} + U\right\}
$$

That is, $f(i)$ is the index of the first element after $i$ to go outside the bounds, or $nil$ if there is no such element.

For example, with $R = 6, U = 2, L = 1, W = 3,$ the sequence

$[0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0] \to [3, 4, 5, nil, nil, 7, 8, 9, 10, nil, nil]$

Here is the simple $O(N W)$ solution in Python:

def breakout(a: Sequence[int], upper: int, lower: int, window: int) -> Sequence[Optional[int]]:
    """For each `a[i]`, compute the (index of the) next element (within a
    `window`) to go above `a[i] + upper` or below `a[i] - lower`."""
    assert upper >= 0 and lower >= 0 and window >= 0
    result = [None] * len(a)
    for i in range(len(a)):
        for j in range(i + 1, min(i + window + 1, len(a))):
            if a[j] < a[i] - lower or a[j] > a[i] + upper:
                result[i] = j
                break
    return result

Does this problem have a name or a more efficient solution?


texts: Does photogrammetry have non-rigid 3D reconstruction methods?

texts:
Prerequisites

I've found out that photogrammetry methods allow us to fetch 3D model from set of images of a scene. I call this rigid reconstruction.

There are methods of finding correspondence between two 3D scans even though scanned object performed non-rigid transformations between scans like Global Correspondence Optimization for Non-Rigid Registration of Depth Scans.

Question

Are there methods for 3D reconstruction by multiple photos, which take into account the fact that object may not only change its translation or rotation, but may also deform? If yes, how are they called and where should I start reading?

E. g., given a video (or videos) of speaking human, take a model of his/her face surface (without generative models and predefined templates); or reconstruct a model of t-shirt, which falls down on the floor and deforms, by series of images.


texts: What happens with trios, full trio, (full) semi-AFL, (full) AFL if we require closure under intersection?

texts:
Wikipedia says:

  A trio is a family of languages closed under e-free homomorphism,
  inverse homomorphism, and intersection with regular language.

  A full trio, also called a cone, is a trio closed under arbitrary
  homomorphism.

  A (full) semi-AFL is a (full) trio closed under union.

  A (full) AFL is a (full) semi-AFL closed under concatenation and the
  Kleene plus.

I am wondering if the four concepts are required to be closed under intersection with regular language, not  intersection with languages in the same family?
why are intersection with regular languages required, not intersection?
I wonder what the concepts are if changing closure under intersection with regular language, to closure under intersection with languages in the same family?

I asked these because I saw that the recursively enumerable languages, recursive languages, context-sensitive languages, regular languages are closed under intersection with languages in the same families, while context-free languages are not.


texts: Classifying infinite languages of encodings of halting Turing machines

texts:
Given this question:

$L$ is an infinite language of encoded Turing machines who always halt.

$L$ might be decidable
$L$ might be in RE but not in R
both 1. and 2. are correct

I know the solution to this question is 3., but I seem to lack the understanding on how am I suppose to get to that solution. Could you explain how should I approach this kind of questions? Am I supposed to start drawing TMs?
Why is the answer is C? What's the indication of that?
It would help me a lot if you could explain to me your thought process when facing this kind of problem.


texts: Will floating point code return the same arithmetical results on two different computers?

texts:
Say I am using boost or the built-in float or double mathematical libraries of my C++ compiler.

I distribute the program.

Will the execution of my C++ program on different machines given different floating point results given that the FPU is CPU specific and AMD may not return exactly the same thing as Intel or ARM.

Should I use fixed-point algorithms to circumvent this possibility?

Would the answer be different if my program was written in something other than C++?


texts: Eliminating useless productions resulting from PDA to CFG converison

texts:
In my class we used a Pushdown Automata to Context Free Grammar conversion algorithm that produces a lot extraneous states.

For example, for two transitions, I am getting the following productions

  $$\begin{gather*}
  \delta(q_0,1,Z) = (q_0,XZ) \\
  {}[q_0,Z,q_0] \to 1[q_0,X,q_0][q_0,Z,q_0] \\
  {}[q_0,Z,q_0] \to 1[q_0,X,q_1][q_1,Z,q_0] \\
  {}[q_0,Z,q_1] \to 1[q_0,X,q_0][q_0,Z,q_1] \\
  {}[q_0,Z,q_1] \to 1[q_0,X,q_1][q_1,Z,q_1] \\
\end{gather*}$$

  $$ \begin{gather*}
  \delta(q_1,0,Z) = (q_0,Z) \\
  {}[q_1,Z,q_0 ] \to 0[q_0,Z,q_0] \\
  {}[q_1,Z,q_1 ] \to 0[q_0,Z,q_1] \\
\end{gather*}$$

How do I decide which state makes it into final production, and which one will be excluded ?


texts: Evaluating correctness of various definitions countable sets

texts:
I was trying to understand the definition of countable set (again!!!). Wikipedia has a very great explanation:

  A set $S$ is countable if there exists an $\color{red}{\text{injective}}$ function $f$ from $S$ to the natural numbers $\mathbb N$.
  If such an $f$ can be found that is also surjective (and therefore $\color{red}{\text{bijective}}$), then $S$ is called countably infinite.
  In other words, a set is countably infinite if it has $\color{red}{\text{bijection}}$ with the $\mathbb N$.

So I summarize:

$S$ is countable iff $S\xrightarrow{injection}\mathbb N$
$S$ is countably infinite iff $S\xrightarrow{bijection}\mathbb N$

But then wikipedia confuses by stating following points:

  Theorem: Let $S$ be a set. The following statements are equivalent:

  $S$ is countable, i.e. there exists an injective function $f : S → \mathbb N$.
  Either $S$ is empty or there exists a surjective function $g : \mathbb N → S$.
  Either $S$ is finite or there exists a bijection $h : \mathbb N → S$.

Q1. I feel 2nd statement is wrong, as it allows some element in $S$ to not to map to any element in $\mathbb N$. That is $\mathbb N \xrightarrow{surjection} S$ does not imply $S\xrightarrow{injection}\mathbb N$. Hence $S$ is not countable. Right?
Q2. 3rd  statement defines countably infinite set, so its countable also. Right?
Q3. Also I dont get if the extra restrictions of emptyness and finiteness in statements 2 and 3 are required.

Wikipedia further says:

  Corollary: Let $S$ and $T$ be sets.

  If the function $f : S → T$ is injective and $T$ is countable then $S$ is countable.
  If the function $g : S → T$ is surjective and $S$ is countable then $T$ is countable.

Q4. Here, too, I feel 2nd statement is incorrect for the same reason as 2nd statement in the theorem. Right?


texts: Minimizing inversions in an array with a single swap

texts:
This was asked in the (very) recently concluded Hackerrank Worldcup. Paraphrased:

  Given a permutation $a$ of integers from $1$ to $N$, how can I
  minimize the number of inversions by a single swap of any two
  integers?

  An inversion is a pair of indices $(i, j)$ such that $i < j$ but
  $a[i] > a[j]$.

I think that this can be achieved by swapping the numbers which have been shifted the most from their position. That is:

If $n_{inv}(a)$ is the number of inversions in a permutation $a$, and $swap_a(i, j)$ is the permutation obtained by swapping the integers at $i$, $j$, then:

$$
\underset{i, j}{argmin} \{n_{inv}(swap_a(i, j))\} =
\underset{i}{argmax} (a[i] -i), \underset{j}{argmin} (a[j] -  j)
$$

In pseudo-code:

leftmost = [-1, -1]        # The first value is the displacement
rightmost = [1, -1]        # The second the index where it occurred
for i in 1..n
    d = N[i] - i           # N being the array of numbers
    if d > leftmost[0]
        leftmost[0] = d
        leftmost[1] = i
    else if d < rightmost[0]
        rightmost[0] = d
        rightmost[1] = i
return leftmost[1], rightmost[1]

The thing is, I have no idea why this is correct, or even if it is. How can I prove that this works?
Or determine the conditions for which it will work?

I have been struggling to understand how I reached this idea and feel that proving it would help me.

To be clear, I am not looking for a solution to the minimizing inversions problem, but only a way to prove that the solution I came up with is correct or incorrect.


texts: Prove the MinAveCodeLen of a product information source is less than the sum of that of the multiplicand and multiplier source?

texts:
The product of 2 independent sources $(S_A,P_A)$ and $(S_B,P_B)$ is defined as

$$
(S,P)\text{ s.t. }S = \{s_As_B|s_A\in S_A,s_B\in B\}\text{ and }\ P(s_As_B) = P_A(s_A)\cdot P_B(s_B)\,\forall s_A\in S_A,s_B\in S_B
$$

and the MinAveCodeLen is the minimum average codeword length which is equal to the average codeword length of a Huffman coding.

The problem is to prove

$$
\mathrm{MinAveCodeLen}(P)\leq\mathrm{MinAveCodeLen}(P_A)+\mathrm{MinAveCodeLen}(P_B)
$$

The original problem is quite confusing. I am asked to prove $H(P_A)+H(P_B)=H(P)$ in the previous part, so I was trying to relate the problem with $H$ at first with no progress.


texts: Permute the subintervals of an interval partition to most closely align with a model partition

texts:
You are given two things: A fixed initial 'model' partition of an interval, e.g.

I------I---I-----I-------I----...

where each - or I represents an element in a discrete time series and the Is are the partition boundaries.  This can also be represented as a sequence of subinterval lengths, i.e. 7, 4, 6, 8, ...

Then, you're given a new set of subinterval lengths; and the task is to arrange these in such a way as to get as many coincident Is as possible.  Or equivalently, you are given a new partition on an interval of the same length (though, critically, the new partition may have greater or fewer elements) and the task is to shuffle the subintervals around to maximize alignment.  So if the model was

I------I---I-----I-------I----I

and you are given 2, 11, 5, 12, i.e.

I-I----------I----I-----------I

then the solution would be 11, 2, 12, 5,

I----------I-I-----------I----I
           *             *

achieving alignment at 2 locations (marked with an asterisk, compare to model).

There is an additional constraint: The locations of the aligned subintervals must be distributed approximately randomly throughout the length of the solution.  The simplest means of getting a partition with at least some alignment to the model would be to build the new partition segment by segment, drawing without replacement from the collection of test segments, aligning where possible.  But this would strongly bias the occurrences of alignment towards the beginning of the time series, and is therefore not allowed.  There is of course also the brute force O(n!) enumeration but my series are little too long for that.

Naturally a solution that finds the optimal permutation would be great, but one that is efficient and gets a permutation with a substantial fraction of the possible alignment would also be good.  My current version is a variation on the 'simple' algorithm derived above, except only drawing from a small subcollection of subintervals so as to avoid bias.  I know it can be improved upon!


texts: Splitting a node in B+ tree with odd number of keys

texts:
This and several other resources suggest to "Always a node that gets the middle key from bottom splits, should drop one item for a new middle key".

To illustrate with an example.

For 5-way B+-tree,

(24, 25, 44, 79) is one of the leaf nodes with its root being (..,24,80,...)

(..,24,80,...)
      \
       \
        \
       (24, 25, 44, 79)

After Inserting 40.

The node (24, 25, 40, 44, 79) gets overloaded and is forced to split(considering the siblings are full as well).

In such a case, is there any advantage of splitting it as

(24, 25)   (40, 44, 79)
over (24, 25, 40)   (44, 79)

Is this split A

(..,24, 40, 80,...)
         | \
         |  \
         |   \
    (24, 25)  (40,44, 79)

better than this split B?

 (..,24, 44, 80,...)
          | \
          |  \
          |   \
 (24, 25, 40)  (44, 79)

If so, what makes A correct and B wrong, considering that both are satisfying the rules of the B+ tree.

I couldn't find any resource to back my argument that B is equally correct as A.


texts: Non-trivial tractable properties of triples

texts:
Many intractable $NP$-complete problems can be modeled as deciding whether a set of triples, $F=${$t_1, t_2, ..., t_n$} where each triple $t_i$ is a subset of three elements over base set $U=${$a_1, a_2, ..., a_k$}, satisfy some non-trivial property. For example, 3-edge coloring of cubic graphs can be modeled as the problem of deciding whether sets of triples satisfy that the elements in each triple must have different color.

I'm looking for examples of non-trivial tractable properties ($P_2$) of sets of triples (which have polynomial time algorithms) given that the sets of triples already satisfies some other non-trivial property $P_1$. Non-trivial property means that there are infinite number of sets of triples that satisfy the property and infinite number of sets of triples that do not. Are all non-trivial properties $P_2$ of sets of triples intractable?

Also, I'd appreciate a survey on the subject.

EDIT: Based on Ben's answer, I added the requirement that $F$ already satisfies some non-trivial property $P_1$ and we are asking weather it satisfies another no-trivial property $P_2$. For instance, in the 3-edge coloring example, the family of triples $F$ must represent the edges incident on the nodes of a cubic graph.


texts:
I have a complex function, which looks something like this:

$$f(x) = \sum_{k=0}^x{\frac{g(k)}{h(k)}} + l(x)$$

Now, $g(k) = O(\log k)$ and $h(k) = O(k)$, the sum iterates $k$ from $0$ to the parameter $x$ and $l(x)$ is meant to provide a decimal correction, but its form is $\dfrac{a^{b-x}}{h(k)} (a,b - const)$.

How can I assess the big O of $f(x)$?

I did some calculations and came up with $O(x^2 \log x)$, but I'm not confident it is right.


texts:
In a Binary Tree, can two nodes have the same value? For example:

     3
    / \
   4   4
  / \
 1   2

They are two different nodes, but they have the same value. Here is code:

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

const r = new TreeNode(3);
r.left = new TreeNode(4);
r.right = new TreeNode(4);
r.left.left = new TreeNode(1);


texts: What is the name the class of functions described by O(n log n)?

texts:
In "Big O", common notations have common names (instead of saying, "Oh of some constant factor"):

O(1) is "Constant"

O(log n) is "Logarithmic"

O(n) is "Linear"

O(n^2) is "Quadratic"

O(n * log n) is ???

Is it just "n log n" or does it have a special name like the above?


texts: "Applicative order" and "Normal order" in lambda-calculus

texts:
Applicative order: Always fully evaluate the arguments of a function
  before evaluating the function itself , like -

  $(\lambda x. x^2(\lambda x.(x+1) \ \ 2))) \rightarrow (\lambda x.
 x^2(2+1))\rightarrow \  (\lambda x. x^2(3)) \rightarrow \  3^2 \
 \rightarrow \ 9$

  Normal order: The expression would be reduced from the outside in ,
  like  -

  $(\lambda x.x^2 (\lambda x.(x+1) \  2)) \rightarrow \ (\lambda x.(x+1)
 \ \ \   2)^  2 \rightarrow\ (2+1)^2 \ \rightarrow 3^2 \ \rightarrow \
 9 $

Let $M = (\lambda x.y \  (\lambda x.(x \  \ x) \  \lambda x.(x \ \  x)))$

Why is it that under applicative order, $M \rightarrow$  infinite loop,
but under normal order, $M \rightarrow y$?


texts: Is developing an OCR considered a research project?

texts: Is developing an optical character recognition system for an alphabet which has no previous ocr considered a reputable conference or journal worthy research project, given the fact that there are so many commercial ocr system? Though, lots of conference proceeding and journal entries shows up when googled, but most of them are old and are about performance of a specific algorithm. There are also research on ocr for cursive alphabets which are hard to segment, like Arabic. The alphabet I am developing ocr for is of Indic origin and cursive as my final year undergraduate thesis. So, I'm wondering if it's a good research project.


texts: Given a graph $G(V, E)$ and two matchings $M \subset E$ and $M' \subseteq E$ with $|M'| > |M|$, how can one prove that  $M\oplus M'$ ($\oplus$ denotes the symmetric difference) must contain at least $|M'|-|M|$ augmenting paths of $M$? I know that there have to exist some $M$-augmenting paths since $M$ is not a maximum matching, but I don't really know how to prove the above.


texts: How to properly calculate dependent nested loops for big-O

texts:
I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, both of which iterate $n$ times, the order will be of $n^2$; but if we have a dependent nested loop such as:

input = an n-dimensional array
For i = 0; i < n; i++:
        For j = 0; j < i; j++:
            ...

Am I correct in thinking this would always be $O(n^2)$ as in the worst case, this loop will always be $n^2$?

The lecturer gave us the forumla $\frac{1}{2}n(n+1)$ but has not explained in what context this is to be used for calculating the running time of a 2-nested loop with dependency. Is there a general way to calculate the running time of a dependent nested loop, like there is with standard nested loops?


texts: Determining if an integer appears more than $n/2$ times

texts:
What is the minimum number of comparisons required to determine if an integer appears more than $n/2$ times in a sorted array of $n$ integers?

I am trying binary search on the array A.

Algorithm(A):

x = A[mid], where mid is the middle element of the array.
Compare x with A[n/4] and A[3n/4].
If x = A[n/4] and x ≠ A[3n/4] then search in A[1] to A[3n/4 + 1].
If x ≠ A[n/4] and x = A[3n/4] then search in A[n/4 + 1] to A[n].
If x ≠ A[n/4] and x ≠ A[3n/4] then it is a no instance.
If x = A[n/4] and x = A[3n/4] then it is a yes instance.

Running Time: $T(n) = T(3n/4) + O(1)$ which is $O(\log n)$ in asymptotic sense. At each step I am doing two comparisons so $2\log_4n$ if $n = 4^k$.
Is there any better (optimal) algorithm to solve the problem mentioned above?

Also, I don't know how to prove the lower bound.


texts: Turing machine with semi infinite tape - Prove by construction

texts:
I'm studying constrained Turing Machines.

There's a theorem that proves that both infinite and semi-infinite tape TM have the same computational power. The theorem that proves this by emulating a TM1 with infinite tape with a multi-track tape TM2, where one track emulates the right part of the TM1 tape and the other track emulates the left part TM1 tape.

Could I emulate the infinite tape machine the following way:

Let the alphabet of TM1 be {0,1}
Construct a TM2 machine with semifinite tape to right with alfabet {0,1} U {#}
Let w = 011101
When execution starts, the tape looks like
|011101BBB...
The first step of TM2 should be to call a subrutine TM2 that shifts w on the tape N times to the right and puts # in the first position of the tape, so: |#BB...011101BBB...
If during execution the control unit reads the # symbol, then call again the shifting subrutine.

I know this is not a formal prove, just an idea. I also know that this is not efficient nor an elegant construction but, could it work?


texts: Implementing mathematical theory of arithmetic in Haskell via Curry-Howard correspondence

texts:
I have to ask for forgiveness in advance if the whole question doesn't
make a lot of sense, but unfortunately, I have no better intuition as
of right now and this seems like the best starting point I could come
up with.

I'm reading Tarski's book "Introduction to Logic: and to the
Methodology of Deductive Sciences", I'm on Part VII Chapter 43
"Primitive terms of the theory under construction; axioms concerning
fundamental relations among numbers". It begins by laying out an
elementary mathematical theory of arithmetic of real numbers.

The primitive terms are:

real number (denoted as variables like x, y)
is less than (<)
is greater than (>)
sum (+)
N meaning "the set of all numbers". Thus, an expression "x is a
number" would be written as x ∈ N
is not less than (≮)
is not greater than (≯)

Among the axioms of the theory under consideration, two groups may be
distinguished. The axioms of the first group express fundamental
properties of the relations less than and greater than, whereas those
of the second are primarily concerned with addition. For the time
being, we shall consider the first group only; it consists, altogether,
of five statements:

AXIOM 1. For any numbers x and y (e.g., for arbitrary elements
of the set N) we have: x = y or x < y or x > y
AXIOM 2. If x < y, then y ≮ x
AXIOM 3. If x > y, then y ≯ x
AXIOM 4. If x < y and y < z, then x < z
AXIOM 5. If x > y and y > z, then x > z

Our next task consists in the derivation of a number of theorems from
the axioms adopted by us:

THEOREM 1. No number is smaller than itself x ≮ x
THEOREM 2. No number is greater than itself: x ≯ x

Now I have to stop and finally explain my intentions. I've heard many
times about a so-called "Curry–Howard–Lambek correspondence", and it
made sense whenever I've read examples of it. I am also not
comfortable with manually writing out the reasoning to prove the
theorems, I'd like the machinery of going through reasoning steps to
be checked by a computer for me.

So, I tried to encode the terms, axioms and potentially theorems (got
stuck earlier) in Haskell, but I failed in many ways. I won't show you
all the examples of what I did, but here's the most naive approach of
encoding propositions as types and their proofs as programs:

data Nats
  = NatX
  | NatY
  | NatZ

x :: Nats
x = NatX

data OpGt =
  OpGt Nats
       Nats

data OpLt =
  OpLt Nats
       Nats

data OpEq =
  OpEq Nats
       Nats

data OpNotLt =
  OpNotLt Nats
          Nats

data OpNotGt =
  OpNotGt Nats
          Nats

data Ax1Res
  = Ax1ResLt OpLt
  | Ax1ResGt OpGt
  | Ax1ResEq OpEq

-- how to implement best?
ax1 :: Nats -> Nats -> Ax1Res
ax1 = undefined

-- this doesn't describe the x and y in the type
ax2 :: OpLt -> OpNotGt
ax2 = undefined

This piece of code brings more questions than it gives answers:

should axioms be implemented or kept as unimplemented functions
which we just assume to exist?
how do I limit the implementation of my functions to only rely on
available theorems and axioms if I can construct basically any term?
Should I hide the constructors?
types should obviously contain variables like x and y, I tried
that in other approaches but that gets even hairier

My questions are:

what would be a proper implementation of such proofs in Haskell?
what materials should I read in order to make a proper
implementation myself and understand the topic better?

I hope the vagueness and my level of ignorance in the question will not
put you off from answering it. Thank you!


texts:
I have a weighted graph representing traffic network. Nodes represent the locations and vertices represent available paths between locations. Weight values represent number of the passages on the path.

I would like to cluster based on the similarity of the weight values (i.e. number of passages) and establish different traffic frequentation zones. The weights in different zones are roughly similar except for a few outliers.

In the clustering techniques I've seen the methods often involve using weights as a "distance" between the nodes and finding the best way to split the graph based on the distance and connectivity.
Here, I'm trying to cluster nodes according to the weights of the edges linking them. For example there are certains zones in the graph where all the nodes are connected by vertices with weights of ~4, these should form one cluster, and in another distinct part of the graph the weights are ~1, this forms another cluster.
Do you know any methods for this?

Perhaps my problem is not well suited to graph theory.


texts:
Are Interrupts really just an abstracted form of polling?

I saw a system-file-watcher library that stated it used polling, as opposed to listening for events. Is the .NET framework SystemFileWatcher class just an abstraction of polling?

In a computer, interrupts are stacked, and the CPU checks the interrupt stack after every cycle, so this is pretty much polling, right? - Albeit more efficient than checking every individual device.


texts:
Got a problem I'm not sure how to approach.
I'm being given a string of text with indeterminate length, around typical "body text" size. The text is a solid color, and the background can be a solid OR a gradient of one or more colors of varying luminance. The goal is to make the text readable across the entire background while adjusting the color channels as little as possible.
How could I find the SMALLEST possible color adjustments to the foreground and/or background that would make the text readable, according to WCA standards or others?


texts: Show that the Turing Machine domain can be viewed as a classical planning domain

texts:
This is one of my assignments. I am not able to comprehend how to reduce the Turing machine domain to Classical planning domain. My understanding is that we have to essentially perform complexity analysis of classical planning domain. So I have defined these two languages

a)  PLAN-EXISTENCE(D) = {P : P is the statement of a planning problem that has a solution}

b)  PLAN-LENGTH(D) = {(P,n) : P is the statement of a planning problem that has a  solution that contains no more than n actions (length ≤ n) }

And then I proceed to prove that both these are decidable in classical planning domain.

Is this the correct approach? Please help me


texts:
Suppose we are given a directed weighted graph $G=(V,E)$, a source vertex $s$ and the value of the cheapest path $\delta(s,v)$ for every $v \in V$.

I want to find an algorithm for the shortest path tree rooted in $s$ with time complexity of $O(V+E)$.

We may assume that all vertices are reachable from $s$.

I thought of running something like BFS traversal on $G$ and for each vertex $u$ I examine, for each neighbor $v$ of him, I'll check that $\delta(u)+w(u,v)=\delta(v)$ and if so, I'll add $(u,v)$ to the output SPT.

Is that sounds right? or has any pitfalls I haven't thought about?
If so, how would you prove that? by induction?


texts: Constructing a Divide and Conquer Algorithm

texts:
I'm thinking of using something similar to the Merge Sort algorithm. So the recurrence running time of Merge Sort is T(n) = 2T(n/2) + n. What should I do about if n/2 is less than or equal to m, OR if n/2 is greater than or equal to m?

I believe the given function should be location inside the "Merge" function of the Merge Sort.(Since we're merging a sorted array) Thank you for your time.

Edited:
I'm thinking if n/2 is less than or equal to m, use the "Given" function . Otherwise use the original "Merge" function (The usual Merge for Merge Sort)


texts:
Im studying some properties of Boolean Algebra and found the Operation Linkage Laws.

Im not able to understand how this laws are possible, and the remark on the proof is not really clear for me. Can any one show me the proofs of this laws or share any resources where I can find a more detailed proof of the laws?


texts: Bubble sort: how to calculate amount of comparisons and swaps

texts: For a given sequence 1, N ,2 ,N −1 ,3, N −2, ... I want to calculate the number of comparisons and swaps for bubble sort. How can I accomplish that using $\theta ()$ notation? I would know how to do it for any sequence, but not for a given one.


texts: what is the function of a turing machine

texts:
The main question asked me to build a certain turing machine such that given a word w over {0,1}*
the turing machine accepts all such words and ends in accept state with the tape string = the word apended with the number of zeros in it. I built the state diagram of this turing machine..
But now there is a question next to it which say something like -

What is the function the machine you build computes ??

I dont understand what this means ?? What i can think of is that the function the question talks about is the transition function... and that just copies 0's from w to the end of it...
it doesnt computes as such anything..
Any lights on the above ??
Thanks


texts: The Gas Station Problem - fast implementation

texts:
Recently I was asking about the algorithm to solve The Gas Station Problem and I got useful answer. Unfortunately solution with transforming a graph to complete graph and then preparing another one to find the shortest path (as described in paragraph 4) is really slow in case of my constraints.

I figured out how to implement much faster version. It's way better, but has a bottleneck :-(. Let me first describe my implementation. It's really simple:

I use BFS and relaxation method to calculate D[destination][0]:

D[v][f] - minimum cost to get from u to v with remaining f units of fuel at this city.

minFuel - minimum remaining fuel at v = max(0, f1 - distance(u,v))
maxFuel - maximum remaining fuel at v = tankCapacity - distance(u,v)

D[source][0] = 0
D[v][f] = min((u,v), f1, f2 | u->v in Edges and f1 in 0..tankCapacity and f2 in minFuel..maxFuel)
             { D[u][f1] + (f2 - f1 + distance(u,v)) * fuelRate[u] }

The bottleneck is because of going through all possible values (f1, f2).

Pseudocode:

queue.push(source);
D[source][0] = 0
visited[source] = true

while(!queue.empty)
    current = queue.pop

    foreach (current,v) in Edges
       if !visited[v]
           queue.push(v)
           visited[v] = true

        for f1 in 0..tankCapacity
           if D[current][f1] == infinity
              continue

            minFuel = max(0, f1 - distance[current,v])
            maxFuel = tankCapacity - distance[current,v]

            for f2 in minFuel..maxFuel
                toRefill = f2 - f1 + distance[current,v]
                newCost =  D[current][f1] + toRefill * fuelRate[current]
                if (newCost < D[v][f2])
                   D[v][f2] = newCost

return D[destination][0]

Constraints (only integers):

maximum vertices:      1000
maximum edges:         10000
maximum distance:      100
maximum fuel rate:     100
maximum tank capacity: 100

Does anybody have an idea how to improve this algorithm to make it faster?


texts: Difference between Parallel and Concurrent programming?

texts:
When looking at concurrent programming, two terms are commonly used i.e. concurrent and parallel.

And some programming languages specifically claim support for parallel programming, such as Java.

Does this means parallel and concurrent programming are actually different?


texts: Determine if there exists a line that intersects all horizontal segments. Better than $O(n^2 \lg n)$?

texts:
Suppose I have $n$ horizontal segments in the plane (i.e. their end points share the same $y$ value). I want to determine if there exists a line that intersects all such segments.

I think I can assert that (by some argument based on shifting the line), there exists such line iif there exists a line positioned on some end-point of one of the line segments that intersects all line segments (so that I can iterate through all end-points of the line segments (in total $2n$ points) and try to find the line). Then if I fix a point $p$, I can do a $O(n \lg n)$ radial sweep and see if there exists a line positioned at that point that intersects all the segments. I then just iterate through all $2n$ points and that gives me $O(n^2 \lg n)$.

Is my reasoning correct enough for me to write an algorithm for this?
Is there a better way to do this than $O(n^2 \lg n)?$


texts: Finding reduction to prove that a language is NP-complete

texts:
I need to prove that the following problem is NP-complete: We have $n$ diplomats from $n$ countries and we need to seat them around a round table. We also get a list of diplomats who don't get along with each other, and we can't seat them next to each other.

I thought about a reduction from the $n$-color graph problem (graph coloring) which is NP-complete, but I'm not sure what the reduction is exactly. Can somebody help with that?


texts: Why is maximum size of root is 2n + 1 in Splay trees?

texts:
In the amortized analysis of Splaying in Dynamic trees, let us consider a splay tree $T$ with $n$ keys   and $v$ be a node of $T$.  We define $size(v)$ as the number of nodes in the subtree rooted at $v$. The size of an internal node is one more than the sum of sizes of its two children. So, the root $T$ has a maximum size of $2n + 1$.

My doubt is how it can be $2n+1$? If a binary tree has $n$ keys, that means it can have a maximum of $n-1$ internal nodes. If we sum up all the sizes (taking size of keys = 0), then maximum size of root turns out to be $2n-1$.


texts: Why can’t a qbit be both entangled and in a pure state?

texts:
Not sure if I should ask this on CS or physics SE, but here goes.

I’m reading on quantum computing, and one thing that keeps confusing me is the following basic fact about QM:

Say we have a qbit A, and a qbit B, then two possible quantum states for $A$ are:

$$|+\rangle=\frac {|0\rangle + |1\rangle}{\sqrt 2}$$

$$\frac {|00\rangle + |11\rangle}{\sqrt 2}$$

In the first case, the qbit $A$ is in a quantum superposition between $0$ and $1$. In the second case, the qbits $A$ and $B$ are ALSO in a quantum superposition, but they are now entangled. I understand that there is a difference between these states, in the sense that the second is an entangled state, whereas the first one is not.

However, what I don’t understand, is why, solely from the perspective of $A$, there is a difference between these states. I read that in the second, entangled state, $A$ (taken as an individual qbit) is not in a superposition state, but in a mixed state. I know that this is a very important basic fact about QM but I still don’t really get it.

why is it not possible for $A$ to be both in an entangled state, AND in a superposition “with itself” (i.e. a pure state, rather than a mixed state). I.e. by what principle of quantum mechanics do we know this, and from what does this principle follow?
Is there an intuition behind this? I.e. how would quantum mechanics no longer make sense if it weren’t the case.


texts: Finding post-order traversal of a binary tree from its in-order and pre-order traversals lower bound

texts:
I know that we can construct a BST by just having its pre-order traversal in $O(n)$ time (this link). But what if the tree is just a binary tree and we have its in-order and pre-order traversals? I could only find a $O(n^2)$ (worst case) algorithm for this problem, like this link.

So I'm wondering whether a $o(n^2)$ algorithm for this problem is found or the $\Omega(n^2)$ lower bound is proven or is finding a reachable lower bound an open problem?


texts:
Is the wall-follower algorithm a poly-time algorithm (for Perfect Mazes)?

In particular, are there poly time algorithms for solving the Perfect Maze problems?

A perfect maze has the following properties:

no inaccessible areas and is simply connected.
no closed loops
one and only one path from any point to any other point.
the maze has exactly one solution.


texts: Behavior of specific PDA for a certain input

texts:
Suppose we're given the non-deterministic PDA shown below which reads from the alphabet $\sum = \lbrace a,b \rbrace$. How will this PDA behave if we pass it the string $ba$? We read $b$ first and push $b$ to the stack, but when we read $a$ I get confused. My assumption is that we fork into two new branches - one in which $b$ was popped and one in which $a$ was pushed. Is this correct? If not, can you tell me where I go wrong?

Thank you very much!


texts: Why sequential consistency model is widely used if it is unsound

texts:
From this talk and these lecture notes here and here I learned that sequential consistency does not actually model what really happens in practice. However, it is also pointed out that most of the work in formal methods assumes the sequential consistency model even though there exists other models which correctly characterize what really happens in practice. I'm unable to understand why the sequential consistency model is widely used if it is unsound with respect to what happens in practice. Is there a good reason for doing this? What confused me even further was that in the textbooks on concurrency theory that I could access (e.g. [1]. [2], [3]), I could not find any references to this topic.

Roscoe, B. (1998). The theory and practice of concurrency.
Bowman, H., & Gomez, R. (2006). Concurrency theory: calculi an automata for modelling untimed and timed concurrent systems. Springer Science & Business Media.
Gorrieri, R., & Versari, C. (2015). Introduction to concurrency theory: transition systems and CCS. Springer.


texts: Need help optimizing an algorithm that's supposed to maximize the greatest common divisor of n elements by removing at most one element

texts:
Alright, first here's the text of the problem:

You're  given n bags of candies where the i-th bag contains a[i] candies and  all numbers a[i] are in the segment [1,m]. You can choose a natural  number x and each second remove x candies from one of the bags if it  contains at least x candies. The goal is to empty all the bags except at most one of them. Find the greatest possible value of x that allows you to achieve this goal.

The desired time complexity is O(n* log m);

What I managed(I think) to do is write an O(n^2 * log m) algorithm (the two nested for loops are O(n^2) and Euclid's algorithm is O(log m)).

The code written in c++ is below. The second for loop calculates the gcd of the numbers excluding the i-th number and I calculate the maximum by considering all values of i, but apparently it can be done linearly.
Any  ideas on how to optimize it to O(n* log m)?

int gcd(int a, int b){
    if(b == 0)
        return a;
    return gcd(b, a%b);
}

int greatestPossibleGcd(int *arr, int n){
    int maxgcd = 0;
    int current = 0;

    for(int i=0;i<n;i++){
        maxgcd = gcd(maxgcd, arr[i]);
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(j == i)
                continue;
            current = gcd(current, arr[j]);
        }
        if(current > maxgcd)
            maxgcd = current;

        current = 0;
    }

    return maxgcd;

}


texts: Would the following grammar be ambiguous?

texts:
I have the grammar $S = aSbS|bSaS|\varepsilon$. When I was first looking at the problem I thought it was unambiguous. When I looked at the answer it said that it was ambiguous. The solution it gave was:

$S \rightarrow aSbS \rightarrow a\varepsilon bS \rightarrow a\varepsilon b\varepsilon \rightarrow ab$

$S \rightarrow aSbS \rightarrow aSb\varepsilon \rightarrow a\varepsilon b\varepsilon \rightarrow ab$

This doesn't make sense to me though because aren't these both producing the same parse tree?


texts:
Given a matrix $A=[a_{ij}]$ of positive number $0\leq a_{ij}\leq1$ that has $m$ rows and $n$ columns. I would like to select, for each row $i$, a set of columns $S_i$ such that $$\sum_{j\in S_i} a_{ij}\geq1,$$ and the number of overlaps $\Delta$ is minimum. The number of overlaps $\Delta$ is calculated as follows: $$\Delta=\sum_{1\leq p<q\leq m}\Delta(S_p,S_q),$$ where, for any pair of columns $(S_p,S_q)$, we have $S_p\cap S_q\ne\emptyset\iff\Delta(S_p,S_q)=1$.

I would like to find an algorithm that minimizes the number of overlaps.

I tried to sort $a_{ij}$ for each $i$ such that $a_{i1}\geq a_{i2}\geq \cdots\geq a_{in}$, then make $S_i=\{1\}$ and verify the sum to be larger than $1$, if not make $S_i=\{1,2\}$, and so on. But, I found a counter-example for this to be non-optimal.


texts: Is the language with decreasing numbers of a, b and c context-free by pumping lemma?

texts:
So I've been given the following language on an assignment.  It is the only question I have left of 10, and I've been racking my brains out trying to solve it for hours.

$$L=\{w:w\in(a+b+c)^*, n_a(w) > n_b(w)>n_c(w)\}$$

where $n_x(w)$ represents the number of character $x$ found in $w$.  The problem statement is: prove or disprove that the language is context-free.  Context-free grammars or pushdown automata are acceptable proofs.  Use pumping lemma to disprove.

I've extensively explored both possibilities and I'm fairly certain that it is context-free.

The approach I've taken in finding a context-free grammar for the language involves using rules which preserve the constraint $n_a(w) > n_b(w) > n_c(w)$ (ie. whenever a $b$ is added, add an $a$; whenever a $c$ is added, add a $b$).  Then, I've attempted to enforce that there are at least two $a$s and at least one $b$ (base case for the constraint).

The grammar I've used is:

$S\implies XaXaXbX | XaXbXaX | XbXaXaX$

$X \implies XX| A | B | C | \lambda$

$A \implies a$

$B \implies ab | ba$

$C \implies abc | acb | bac | bca | cab | cba$

(where $\lambda$ is the empty string)

My grammar fails for strings like $cccaaaaabbbb$.

I'm confused as to where to go from here.

I would really like a push in the right direction, not an answer.
 Any help is greatly appreciated!


texts: Converting a CFG with epsilons into a DPDA

texts:
I have a CFG:

S -> $T$

T -> T+T|T-T|T/T|(T)|CX|I

X -> XX |C|N|_|@

C -> a|b|c|....|z|A|B|C|...|Z|_

N -> 0|1|2|....|9

I -> NI|N

Here @ means epsilon.

The above is a valid arithmetic expression in C++.

I have to convert this to a deterministic PDA (does not read @). I do know there exists an algorithm to convert it to NPDA but I have no clue how to go about converting it to DPDA. Any help would be appreciated. Thanks.


texts: Time complexity of DFS and recurrence relation

texts: Is it possible to compute time complexity of Depth First Search (recursive version) which is O(E+V) using a recurrence relation?


texts: Is P = NP when solutions length is polynomially bounded by instance length?

texts:
I'm currently reading the book "P, NP, and NP-Completeness" by Oded Goldreich. I'm currently reading a chapter that's concerned with the "search version" of the P-vs-NP-problem, that is if finding solutions is harder than checking the validity of solutions.

First, the book defines "polynomially bounded relations" as relations (between problem instances x and their solutions y) where there exists some polynomial p such that the length of the solution is polynomially bounded by the length of the related problem instance (that is |y| <= p(|x|)).

Both the search problem as well as the checking problem are then defined on such bounded relations.

Now I wonder: Doesn't polynomially bounding the length of possible solutions to a given instance mean that there are only polynomially many possible solution candidates, which, when given an algorithm C that checks a solution for its validity in polynomial time, implies that finding a solution can also be done in polynomial time by simply checking each of the possible solutions for its validity?

This would mean that if I can efficiently check solutions of a problem for validity, then I can also efficiently find solutions to that problem. (So, basically P = NP)

Is this conclusion - when only looking at polynomially bounded relations - true? (The book of course says that it's not. If I'd need to bet I'd also bet on the book and not on me...)

If not, where is the error in my reasoning?


texts: Relation between Type Assignment system (TA) and Hindley-Milner system

texts:
Recently I started my studies in type theory/type systems and Lambda Calculus.

I have already read about Simple Typed Lambda Calculus in Church and Curry style. The last one is also known as Type Assignment system (TA).

I'm thinking about the relations between TA and Hindley-Milner (HM), the system in languages like ML and Haskell.

The book Lambda-Calculus and Combinators: An Introduction (Hindley) says that TA
is polymorphic (pag. 119). Is that the same sense of polymorphism in systems like HM and System-F?

TA is said to have the strong normalisation property, so is not turing complete. Languages that use HM system are turing complete, Haskell for example. So must be the case that HM system allows terms like the infinity loop $\Omega$ to receive a type. Is that correct or I'm missing something?

Any way, I would like to know the relation between TA and HM.


texts:
I am looking for geometry algorithm.

I have an axis-aligned box $B$ and a triangle $T$ in 3D space. I want to compute an axis-aligned bounding box of their intersection.

Both $B$ and $T$ are convex polytopes and $B\cap T$ is also convex polytope. I don't need general algorithm, I need something fast and simple.

Have you heard about such an algorithm? Or is it trivial and I can't see it?

I got an idea to "crop" the triangle with each of 6 box's faces. Cropping triangle with each plane can add 1 new vertex, so the resulting object may have up to 9 vertices. Then I compute the bounding box of that object. Am I right? Can it be simplified to get only bounding box output?


texts: How to construct a max heap that preserves insertion order for duplicate elements?

texts:
I have a priority queue (using a max heap) that preserves insertion order for duplicate priorities, such that equal priorities fall back to FIFO behaviour. I'm doing this by creating a node with the value, the priority, and an 'insertion stamp' that is basically an incrementing number on the structure. I'd like to remove the need for this stamp, but I'm not sure if it's possible.

How might this work?


texts: Advantages (from a mathematical perspective) of representing data as symmetric matrices

texts:
From Wikipedia, a symmetric matrix is a square matrix that is equal to its transpose. An example of this (I think) is an adjacency matrix with undirected edges, which is a square matrix representing links between elements (undirected in this case).

The thing is, the data is duplicated in this case (looking at it from a computer science perspective). The two halves of the diagonal carry the same information, so you can just use one half of it.

I am new to matrices, so I apologize if this is a basic question. The question is if there is any advantage mathematically or from a computer science perspective to representing data (such as graphs, but more generically any data such as key/value pairs or pointers, etc.) using symmetric matrices like this. Wondering if it (for example) makes lookup O(1) in certain cases, or it provides some other significant hidden benefit because of the symmetry.


texts: Constructing a monad via type synonyms of a particular kind

texts:
We can define a reader/environment monad on the simply-typed lambda calculus, using the following three equations, where $r$ is some fixed type, $\alpha$ is any type (I subscript some terms with their types), $\mathbb{M}$ is the proposed monadic type modality), $\eta$ is the unit of the monad and $\mu:\mathbb{M} \mathbb{M}\alpha → \mathbb{M}\alpha$ is the join of the monad:
$$\mathbb{M} \thinspace α = r → α  \hspace{1cm} ∀α$$
$$ \eta \, a_{\alpha} = \lambda c_{r}.\; a \hspace{2cm} ∀a_{\alpha}$$
$$\mu\,b_{\mathbb{M}\mathbb{M} \alpha} = λc_{r}.\; b_{\mathbb{M}\mathbb{M}\alpha}\, c\, c \hspace{1cm} ∀b_{\mathbb{M}\mathbb{M} \alpha} $$
Can we always construct a reader monad by type synonyms of the form $r = x$, for arbitrary function types $x$ (for example, where $x$ is $((\beta \to t) \to t$), for some type $\beta$?


texts: Finding the Convex Layers of a given set of points

texts:
Definition of convex layers can be found at wikipedia.
 I was trying to understand this algorithm , which works in O(n log n) time, which is optimal.

In the paper, the author has described two types of deletions, among which
one is direct deletion.

In direct deletions, the author deletes the a point of the previous Convex Layer, from the Hull Graph( an endemic concept). The author has written something about Direct Deletions that I didn't understand:

" In general, a pulling operation will be accomplished by conceptually replaying the previous two pulling operations. This replay might be necessary in order to guide the current tangent on it's way down, and in particular find at little cost the vertices over which it must fold."

Where,
Hull Graph: A union of the upper(resp. lower) chains of the subsets of vertices of the given set of points.
Pulling operation: Deletion of edges that are connected to the vertex to be deleted in the hull graph(called tangents).

I would like to know how can the line in bold  be accomplished. Moreover, there's a keen interest of mine to implement this algorithm. Would that be irrational, given the hardness of this algorithm?

Thanks.

Any reasonable help about this paper is appreciated.

Moon


texts: How does Command Z work through computer commands? What is the step by step computer commands that complete the process?


texts: Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

texts:
I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou's textbook), based on diagonalization.

While the proof is convincing (I understand each step of it), it is not intuitive to me in the sense that I don't see how someone would derive it, starting from the problem alone.

In the book, the proof goes like this: "suppose $M_H$ solves the halting problem on an input $M;x$, that is, decides whether Turing machine $M$ halts for input $x$. Construct a Turing machine $D$ that takes a Turing machine $M$ as input, runs $M_H(M;M)$ and reverses the output." It then goes on to show that $D(D)$ cannot produce a satisfactory output.

It is the seemingly arbitrary construction of $D$, particularly the idea of feeding $M$ to itself, and then $D$ to itself, that I would like to have an intuition for. What led people to define those constructs and steps in the first place?

Does anyone have an explanation on how someone would reason their way into the diagonalization argument (or some other proof), if they did not know that type of argument to start with?

Addendum given the first round of answers:

So the first answers point out that proving the undecidability of the halting problem was something based on Cantor and Russell's previous work and development of the diagonalization problem, and that starting "from scratch" would simply mean having to rediscover that argument.

Fair enough. However, even if we accept the diagonalization argument as a well-understood given, I still find there is an "intuition gap" from it to the halting problem. Cantor's proof of the real numbers uncountability I actually find fairly intuitive; Russell's paradox even more so.

What I still don't see is what would motivate someone to define $D(M)$ based on $M$'s "self-application" $M;M$, and then again apply $D$ to itself. That seems to be less related to diagonalization (in the sense that Cantor's argument did not have something like it), although it obviously works well with diagonalization once you define them.

P.S.

@babou summarized what was troubling me better than myself: "The problem with many versions of the proof is that the constructions seem to be pulled from a magic hat."


texts:
I've been reading Garey-Johnson book Computers and Intractability and I am focusin on Section 3.2, Techniques for proving NP-completeness. In these definitions and explanations nothing is formally defined. I was wondering, how would someone define those techniques formally?
The techniques mentioned are restriction, local replacement, and component design. Here are some relevant excerpts:

Proof by restriction is the simplest, and perhaps the most frequently applicable, of our three proof types. An NP-completeness proof by restriction for a given problem $\Pi \in \mathrm{NP}$ consists of simply showing that $\Pi$ contains a known NP-complete problem $\Pi'$ as a special case.
In proofs by local replacement, the transformations are sufficiently nontrivial to warrant spelling out in the standard proof format, but they still tend to be relatively uncomplicated. All we do is pick some aspect of the known NP-complete problem instance to make up a collection of basic units, and we obtain the corresponding instance of the target problem by replacing each basic unit, in a uniform way, with a different structure. The transformation from SAT to 3SAT is of this type.
Our last type of proof, and the one that tends to be the most complicated, is component design. The NP-completeness proofs for 3-DIMENSIONAL MATCHING, VERTEX COVER, and HAMILTONIAN CIRCUIT are typical examples of this type of proof. The basic idea is to use the constituents of the target problem instance to design certain "components" that can be combined to "realize" instances of the known NP-complete problem.

What exactly are those "basic units" and "components"?
I was trying to find some literature about those strict and formal definitions, but couldn't find any.
For restriction, can it be defined as a bijection from instance of one problem to another?


texts: Why are data transfer speeds faster with EIDE than IDE? Wouldn't it be slower with the additional conversion of logical block addressing? What did they change to make it faster?


texts: Automata for languages derived from an automaton by number of state visits

texts:
My question in response to this answer: what would the finite automata look like for $L_1$ and $L_0$ in the answer?

I get how the languages are formed; however, since $M_L$ cannot remember how many times it has looped, how does $q$ branch off (if it does) into the two different DFAs for $L_0$ and $L_1$?

Definitions:

$L$ = infinite regular language
$q$ = state within the DFA for $L$, $M_L$, where $M_L$ loops
$L_1$ = {w in A | $q$ is visited an odd number of times}
$L_0$ = {w in A | $q$ is visited an even number of times}


texts: There are functions with f (n) = f (2n) which can't be calculated

texts:
I have to proofe that there are functions defined by $f:\mathbb{N} \rightarrow \mathbb{N}, f(n)=f(2n), \forall n\in \mathbb{N}$, which are not-computable. However I'm not really sure about the correct method.

I thought about a proof by contradiction. Assume each of those functions are computable. Then, by the Church-turing-thesis, there has to exist a TM which can compute every of those functions. Therefore $L(M)=\{code(M) | \text{M calculates this type of function}\}$ would be decidable. However I profed earlier, that this language is undecidable. This would lead to a contradiction, but I'm not sure about the correctness of my profe...

Thank you for your help :)


texts: Proof of NP Completeness of set-partition problem

texts:
I have reduced subset sum problem to set partition problem but do not know whether it is correct and so I need your help.
MY METHOD
In subset sum problem we have to find a subset $S_1$ of set $S$ so that it sums to a number $t$ and in set partition problem we need to find a subset $X_1$ of set $X$ such that summation of numbers in set $X_1$ is half of that in $X$.
So let us take instance of subset sum problem where $t = (\text{sum of numbers in }X) / 2$. If we can solve the set partition problem than we solved the subset sum problem too. But we know that subset sum is NP Complete so subset sum problem is also NP Complete (I know how to prove it is NP).
I am having doubt whether we can make a choice of $t$ like that or not. Please help.


texts:
In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf

Lemma 5 is given as:

  The approximation factor of the modified greedy [scheduling] algorithm is 4/3.

And gives the example:

  Note that 4/3 is essentially tight. Consider an instance with $m$ machines, $n = 2m+ 1$ jobs, $2m$ jobs of length
  $m + 1, m + 2, · · · , 2m − 1$ and one job of length $m$.

does the above example have an error as a proof of lemma 5?

I have been thinking about it over a day.


texts:
The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and physics requires the tiling to satisfy one more condition:

The tiling should satisfy some proportionality, say, Tile 1 should appear with frequency 1/16, Tile 2 with frequency 9/16, Tile 3 with 6/16, Tile 4 with frequency 0...

The most important decision problem is the following:
Could a given set of Tile tile a grid of size NxN satisfying the frequency constraint within a error of +-epsilon.

For example: could the set {Tile 1, Tile 2, Tile 3, Tile 4} tile the NxN grid with frequency 1/16+-0.01, 9/16+-0.01, 6/16+-0.01, 0+-0.01 respectively....

From one of my previous post:

Algorithms for NP complete problem

I realize the decision problem of tiling without such constraint could be modeled by SAT... With this constraint the problem becomes ridiculously difficult and I eagerly seek for solutions towards this finite decidable problem.... (we could forget epsilon for a moment if the problem with epsilon is too hard)...

So here is the question: how do we model this problem in MIP or SAT or any other optimization algorithm?

For more detail why this problem is practical in material science and physics, see my previous post:

coloring in lattice

reference for wang tile

Computational approach deciding whether a set of Wang Tile could tile the space up to some size

P.S. this is a bounty question from mathoverflow without yet a applicable solution...

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality


texts: Auxiliary random variables in the analysis of the private information of wiretap channels

texts:
I am following Section 13.2 of Mark Wilde's book. I reproduce the question here for completeness.

Consider a wiretap channel $X\rightarrow Y,Z$ defined by the conditional probabilities $p(y,z|x)$ for inputs chosen according to some $p(x)$. The goal of maximizing private information is to transmit information from $X$ to $Y$ without any information leaking to $Z$. Naively, one would say this is simply

$$\max_{p_{X}(x)}I(X:Y) - I(X:Z),$$

where for any channel $A\rightarrow B$ with input chosen according $p(a)$ and symbols transmitted according to $p(b|a)$, $I(A:B)$ is the mutual information between $A$ and $B$ and given by

$$I(A:B) = \sum_{a,b} p(a,b)\log\left(\frac{p(a,b)}{p(a)p(b)}\right)$$

However, the correct way to think about this is to introduce an auxiliary variable $U$. Alice (the sender at $X$) decides $x\in X$ based on $u\in U$. That is $p(x) = \sum_u p(x|u)p(u)$. The private information is defined as

$$\max_{p_{U,X}(u,x)}[I(U:Y) - I(U:Z)]$$

The question is why one needs to introduce the auxiliary variable? I don't really have either intuition or a mathematical proof so any pointers are appreciated!


texts: "problematic" non-halting inputs for Turing machines

texts:
Let us start this question out, by defining for a Turing machine, the set of words it doesn't halt on.
Define: $P(M)=\{w\in\Sigma^*|M$ doesn't halt on $w \}$

We know that the $HALT$ problem is $RE\setminus R$ - thus every TM $M$ that computes $HALT$ has a word it doesn't halt on, i.e $P(M)\ne\emptyset$.

From this, arises the (simple)  question:

$Q(1):$ "is a problem undecidable if and only if every TM that computes it has a non empty 'problematic' set $P(M)$?" $ ^{Q\space(1)}$

Moreover, let's note that for the $HALT$ problem we know that given $M$ that computes it, there are infinitely many inputs it will never halt on (I encourage to think why this is so, before proceeding in the post)

So, similarly we might want to ask ourselves the (slightly) harder version of the first question.

$Q(2):$ "is a problem undecidable iff every TM $M$ that computes it has $|P(M)|=\aleph_0$?" $ ^{Q\space(2)}$

Moreover - let's ask an even stronger question:

$Q(3):$ "if $L$ is undecidable, will we still be able to find a finite set of Turing machines $M_1,...,M_n$ that compute $L$ and have $\bigcap_{k\space=\space0}^nP(M_k)$ finite? what about an infinite set of Turing machines that satisfy that?" $ ^{Q\space(3)}$

And our final (and half-open) question will be:

$Q(4):$ "What else can we understand about Turing machines and their problematic sets?"


texts:
Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$

My first intuition is "Yes", since we may look at $M_1, M_2$ which accepts $L_1, L_2$, respectively. Then, WLOG there's $w$ such that $M_1$ doesn't halt for, and so the machine $M$ which runs $M_1, M_2$ in parallel, may not halt.


texts: What is the connection between the logic and the logic programming?

texts:
As I understand, then logic (i.e. particular theory of logic with some theory's axioms and some possible assignments of the variables) describes some specific world (in the non-modal case) or some set of related worlds (in the modal case) and deduction just explores this one world (this set of related worlds) and discovers/constrains the possible values of the variables (SAT problem).

But logic programming with its quite confusing implication relation (I still don't understand how the implication of the logic programming is related to the implication connective in the logic - those seem to be two completely different notions and different signs - am I right?) allows traveling among worlds (in modal case - among sets of related worlds): if variables {x} has some values in the one worlds, then those variables {x} has some different values in the other world. And it is the (one) semantics of the logic programming, that set of clauses that allow such traveling among worlds, at the end lands the traveller in one world that is fix-point for this set of clauses (of logic programming statements).

Computation is state transition: from one state to the other, from one world-state/world to the other world-state/world. But logical inference is just exploration of one world - be it discovery of the new relations among variables or statements (discovery of theorems) of be it discovery of the consistent set of assignments to the variables (discovery of the solution to SAT problem).

Am I right? What else can be added to this understanding between logic and logic programming?

Maybe there is some logic which allows to deduce the logic programs? To do the reasoning about the logic programs?


texts: How to eliminate for/if/while from algorithms when it's possible

texts: Is there any way to find out how to replace for/if for elementary recursive algorithms? I know that primitive recursive functions cannot basically eliminate "for", but for elementary recursive functions, there must be a way to convert the program into ones that do not have for/if/while and so on (which is elementary recursive).


texts:
I'm trying to understand a small proof in an article about computing lumpability on Markov chains. There is a small detail that I cannot understand, i.e. I don't think it follows from the argument.

The article is Simple $O(m\log{n})$ Time Markov Lumping written by Valmari & Franceschinis.

Given a weighted graph they define the notion of compatible partition of its nodes. Which is a partition $P$ such that for all $B, B' \in P$ and all $s_1, s_2 \in B$ we have that:

$$
W(s_1, B') = W(s_2, B')
$$

They describe an algorithm to compute the coarsest refinement of an initial partition that is compatible (the coarsest croip= compatible refinement of initial partition). The algorithm follows the idea of Paige and Tarjan to compute bisimulation: we take a block $S$ from the partition as a splitter and check whether some other block $B$ breaks the condition above, and if it does we split $B$ into $B_1, \ldots, B_k$ such that the $B_i$ satisfy the condition above when taking $B' = S$.

How exactly these checks are performed shouldn't be essential for the correctness of the algorithm. In the proof of correctness they prove the following lemma:

  Lemma 2. Let $d_1, d_2$ be nodes of the graph. If the algorithm ever puts $d_1$ and $d_2$ into different blocks, then there is no
  croip where $d_1$ and $d_2$ are in the same block.

The proof for when the algorithm separates $d_1$ and $d_2$ during its execution is the following:

  Proof. We show that it is an invariant property of the main loop of the algorithm (that is, always valid on line 2*) that if
  two states are in different blocks of the algorithm, then they are in
  different blocks in every croip.

  If $d_1$ and $d_2$ are in different blocks initially, then they are in
  different blocks in $I$ and thus in every croip.

  The case remains where lines 14 to 20 separate $d_1$ and $d_2$ to
  different blocks.

  This happens only if $W(d_1, S) \neq W(d_2, S)$. Let $P$
  be an arbitrary croip. It follows from the invariant that each
  block of $P$ is either disjoint with $S$ or a subset of $S$,
  because otherwise the algorithm would have separated two states that
  belong to the same block of a croip. Therefore, there are blocks $S_1 , \ldots, S_k$ in $P$ such that $S_1 \cup \cdots \cup S_k = S$. The fact $W(d_1, S) \neq W(d_2, S)$ implies that there is $1 \leq i \leq k$ such that $W(d_1 , S_i) \neq W(d_2, S_i )$. So $d_1$ and $d_2$ belong to different blocks in $P$.

I have a problem understanding the text in bold. To me: it's simply false.
They justify it saying otherwise the algorithm would have separated two states that belong to the same block of a croip.

However:

we still haven't proved the algorithm correct, so I don't really see how the algorithm doing something should imply anything at this point
I don't get if the two states separated are $d_1$ and $d_2$ or if they are referencing other states

So, I see this as a non sequitur, which would invalidate the proof of this lemma and thus the whole correctness proof of the algorithm.

Given that the algorithm was developed to fix a wrong algorithm published previously from other authors, I believe Valmari and Franceschinis were very careful in the proofs, so I'm probably missing something trivial. Can anybody point out what I'm missing?

* The algorithm is simply a main loop that chooses a new splitter $S$ for each iteration and splits all the blocks in the partition and goes on.


texts: Showing the language of TMs that halt on a decidable set of words is not in RE

texts: I need to show that the following language, L = {$\langle M \rangle$ | The set of words which M halts on is decidable}, is not recursively enumerable. In the instructions they advise thinking of a reduction that is similar to the one used in the proof for Rice's Theorem in Sipser's 3rd edition (page 243). I couldn't think of a proper proof by myself. I assume L $\notin RE\cup CO-RE$ so there's no point in trying to prove $\bar{L}$ is in RE to show L is not in RE. Can anyone help?


texts: Turning a simple polygon with holes into exterior-bounded only

texts:
I am converting cartographic objects, which have an exterior boundary (simple polygon) and zero or more interior boundaries (also simple), into a less sophisticated format that specifies exterior boundary only. To overcome this restriction, I plan to “cut through the body of the shape” — joining a pair of nodes of exterior and interior boundary (see figure, left), thus creating a zero-width way into the shape's former interior space that will then technically become exterior (see figure, right).

So the question is: which nodes to join? (Not that it's unacceptable to create new nodes in suitable locations, but undesirable.) An obvious and ideal choice would be the two nodes most close to each other; moreover, I suppose that those would automatically constitute a valid solution — i. e. the new segments won't intersect any existing one. Consequently, the question becomes: how to find the closest node pair?
Googling on this topic yields many results for similar questions which vary in degree of “similarity”, complexity of understanding the algorithm and computational complexity. But most importantly, as far as I noticed, they vary in applicability to input data, — that is, some are designed for convex polygons only, others fail on “overlapping” polygons (I suppose that includes my case, too). So I decided to ask: which algorithms are optimal or at least suitable for my particular task?


texts: Good resources for understanding semidefinite relaxation for combinatorial problems

texts:
I am looking for good, complete and understandable resources in the field of semidefinite programming and combinatorial optimization. Especially I have a combinatorial problem which I want to relax as SDP and want to compare the bound achieved with the LP relaxation. SO I need to know how to formulate a comb opt problem as SDP and also how to argue about the bound. Any resources would be appreciated.

Thanks.


texts: How to perform orthogonal check on two circular binary strings?

texts:
Say we have two circular binary strings $a = a_0a_1...a_{n-1}$ and $b = b_0b_1...b_{n-1}$ with arbitary starting point, and define a and b are orthogonal if $\sum_{i=0}^{n-1}a_ib_i = 0$.
Is there a $O(nlogn)$ algorithm can tell a rotation of such circular binary string is orthogonal to another?


texts: Looking for some lossless compression theory

texts:
I'll apologize in advance if anything in here is ineloquent. Suppose we have a pair of lossless compression (C) and decompression (D) functions.

compressed = C(uncompressed)

and

uncompressed = D(compressed)

Because the system is lossless, it should be expected that any data passed through C will map to a single, unambiguous output. This mapping would essentially be 1:1, otherwise two uncompressed inputs would map to the same compressed output and it would be impossible to determine which one should be chosen on decompression.

Likewise, each compressed input to D should map to exactly one uncompressed output, otherwise the system is not deterministic. This is also like a 1:1 mapping, the inverse of the one above.

In essence, this could be thought of as an encoding, where one input is translated to another output and vice-versa, but with the goal of (most of the time) producing an output with a smaller file size. But for that to work, there must be inputs to C where the resulting compressed size is larger, perhaps significantly so, than the input was.

Put another way: If I had a disk containing every possible 100-byte, 8-bit file, I'd have something like 6.67e242 source bytes of input to C. Although many of the compressed representations would be smaller, it seems like many of the compressed representations would also have to be larger to satisfy the 1:1 relationship. It seems like the total compressed size would be about 6.67e242 bytes, and the mean size of each file would be about 100 bytes. Maybe larger.

The "maybe larger" bit leads to another intuition I had, which says that an ideal decompression function should return an output for every single input. If certain inputs generate an error (i.e. because of data alignment issues, unexpected truncation, checksum failures) that implies that there is wasted space in the mapping that is causing less than 100% optimal usage of the compressed space.

My questions are: 1) Is my understanding about how this works correct? That is, the mean compression ratio of random data is 1.0 or maybe worse, and 2) If a decompression function can fail to decode some input, it is not making total optimal use of the compressed domain?

Are there formal names for this that I can read up on? I feel like this is a problem space that's been well-explored already, but I'd love to see a more formal definition of what is currently a nebulous intuition in my mind.


texts: Simplex algorithm experimental complexity

texts:
For a school project I am doing on linear programming, I've implemented the simplex algorithm in Python.

I was hoping to check the complexity on a number of matrices.

Preferably, they would have to be in standard form ($Ax=b$ and $x\geq0$) (or easily put into standard form) and would have to have a finite inf (to avoid the unbounded case).
Do you have any ideas? Or could you point me torwards a paper or someone who has already done this?


texts: need of error control in transport layer

texts: I want to know why error control is used in transport layer although it is used in data link layer?While data link layer has all data came from upper layers in its frames so its error control should be sufficient.


texts:
I am writing an app which displays speeches on various topics, with each speech having a number of attributes. I want to give the user the choice to sort a list of speeches by an attribute, even within a previously sorted list of speeches.
Consider for example: Suppose the previous list had been sorted by the attribute: "speaker's name", and there were three different speakers (so the list was split into three windows with each window consisting of the same speaker). Now, the user wants to sort the speeches based on the attribute: "length of the speech" such that the new list would now be sorted by speaker's name, and within each window of the speaker's name, the speeches would be sorted by the length (creating a new window within this window for each length of speech in the speaker's window).
I would like to give the user the ability to do this with an arbitrary number of attributes. How can I go about doing such sorting, preferably in the most efficient way?
P.S: I am just a teenage programmer who has been programming for a few years and can understand algorithms in concrete steps - I have not taken college classes in CS, so please keep that in mind when explaining the algorithms.


texts:
We are given a set of $m$ elements $\{e_1,...,e_m\}$ that form our universe $\mathcal{U}$. Each element of our universe is further associated with a positive weight $w(e_j)$ with $j\in \{1,...m\}$. We are further given a collection $S=\{S_1,...S_n\}$ of subsets of  $\mathcal{U}$ whose union equals the universe. The intersection of any two sets in $S$ may be non-empty (i.e. subsets may overlap with each other).

Furthermore,

1) we are given an infinite number of configurations; each configuration can host up to $k$ subsets from $S$. There is no cost for using a configuration.

2) When assigning 2 or more subsets to one configuration and there is an overlap between the sets (i.e. an element is part of more than one set) we pay the weight of that element only once. Obviously, there can be no overlap between subsets when considering different configurations.

Objective:

we want to assign each subset of $S$ to exactly one configuration in such a way that the weighted sum of the elements over all configurations is minimized. Consider the following example:

$\mathcal{U}=\{a,b,c,d,e,f,g\}$,

$w(a)=2$

$w(b)=2$

$w(c)=3$

$w(d)=4$

$w(e)=1$

$w(f)=2$

$w(g)=2$

$S=\{S_1, S_2, S_3\},$

$S_1=\{a,b,c\}, S_2=\{c,d,e\}, S_2=\{e,f,g\}$

$k=2$

In this case, since $k<|S|$, it is obvious that more than one configurations are needed. Moreover,  $S_1$ and $S_2$ should be packed together in the same configuration because of their heavy overlap ($S_1 \cap S_2$ gives the biggest overlap in our example - we pay 3 less cost units). So, the total cost of such an assignment is 12+5=17 and 2 configurations are needed.

Any ideas on how to prove that the problem is indeed intractable? Any ideas on how to calculate a good bound on the number of configurations that are needed?

The unweighted version (when the weights of the elements are all 1) is also very interesting to me. However, I did not manage to find something so far in the literature also for this problem.

Thank you!