texts:
Let $A$ be an $n \times n$ matrix over some field $\mathbb{F}$. The determinant
$$ \det(A) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) A_{1 \sigma(1)} \cdots A_{n \sigma(n)}$$
can be evaluated in $O(n^3)$ field operations (via Gaussian elimination, say).
Note that this is much better than naive evaluation of the polynomial above, which has $n!$ terms.
On the other hand, the similar-looking permanent
$$ \operatorname{perm}(A) = \sum_{\sigma \in S_n} A_{1 \sigma(1)} \cdots A_{n \sigma(n)} $$
has no known polynomial-time evaluation algorithm: it is $\#P$-complete even for matrices containing only zeros and ones over $\mathbb{F} = \mathbb{Q}$. The other significant difference is that the determinant is invariant under an arbitrary change of basis ($A \mapsto P A P^{-1}$ for any invertible $P$), whereas the immanant is only invariant under a permutation of basis elements ($A \mapsto P A P^{-1}$ for $P$ a permutation matrix).
There are a finite number of functions which interpolate between the determinant and the permanent. For any irreducible character $\chi \colon S_n \to \mathbb{Z}$, we can define the immanant of the matrix $A$ to be
$$ \operatorname{Imm}_\chi(A) = \sum_{\sigma \in S_n} \chi(\sigma) A_{1 \sigma(1)} \cdots A_{n \sigma(n)}. $$
Then the permanent corresponds to the trivial character $\chi(\sigma) = 1$, and the determinant corresponds to the sign character $\chi(\sigma) = (-1)^k$ where $k$ is the number of inversions in $\sigma$.

Question: What is known about the complexity of computing immanants? At what point do they switch over from being polynomial time to being NP-hard?

In order for this question to make sense, we need to know about what kinds of immanants arise for a given $n$, or in other words what the irreducible characters of $S_n$ are. It turns out that the irreducible characters of $S_n$ are in bijection with integer partitions of $n$, or in other words decreasing lists of positive integers adding to $n$. These are often also represented by their Young diagrams, for example the integer partitions of $n = 5$ are shown below:

In the standard way of associating partitions to characters, the one-row partition $(n)$ corresponds to the trivial representation (and to the permanent), while the one-column partition $(1, \ldots, 1)$ corresponds to the sign representation (and to the determinant).
There are some natural partial orders that can be put on the set of partitions of $n$, which place the one-row partition at one end of the order and the one-column partition at the other, such as the dominance order. We could perhaps fantasise that as you move up this order from the "easy" determinant to the "hard" permanent, you come across some kind of barrier where computation starts getting harder and harder.


texts:
The run time of binary search is O(log(n)).
log(8) = 3
It takes 3 comparisons to decide if an array of 8 elements contains a given element.
It takes 4 comparisons in the example below.

python2.7

def binary_search(a_list, item, comparisons_inner=0):
    low = 0
    high = len(a_list) - 1

    while low <= high:
        mid = (low + high) / 2
        guess = a_list[mid]
        comparisons_inner += 1
        if guess == item:
            return mid, comparisons_inner
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None, comparisons_inner

my_list = [5, 8, 11, 15, 21, 23, 100, 223]
index, comparisons = binary_search(my_list, 223)
print(index, comparisons)

log(8) < 4
Why is the run time of binary search O(log(n)) despite the 4 comparisons it takes in the example above?


texts: Prove that a boolean function computable in T(n) by a RAM machine is in DTIME(T(n)^2)

texts:
The question is exercise 1.9 from Arora-Barak's book Computational Complexity — A Modern Approach:

Define a RAM Turing machine to be a Turing machine that has random access memory. We formalize this as follows: The machine has an infinite array A that is initialized to all blanks. It accesses this array as follows. One of the machine's work tapes is designated as the address tape. Also the machine has two special alphabet symbols denoted by R and W and an additional state we denote by q_access. Whenever the machine enters q_access, if its address tape contains 'i'R (where 'i' denotes the binary representation of i) then the value A[i] is written in the cell next to the R symbol. If its tape contains 'i'Wa (where a is some symbol in the machine's alphabet) then A[i] is set to the value a.

Show that if a Boolean function $f$ is computable within time $T(n)$ (for some time constructible $T$) by a RAM TM, then is is in $\mathrm{DTIME}(T(n)^2)$.

The trivial solution by using an additional tape recording pairs (address,value) turns out to be in $\mathrm{DTIME}(T(n)^3)$, since that tape can be of size $O(T(n)^2)$ with $O(T(n))$ pairs while the address of each pair can be of size $O(T(n))$.


texts: The class of languages that can be certified in a small amount of space

texts:
NP can be characterized in two different ways, one of them is that it's the class of languages that can be certified by a witness in a polynomial time.

I wonder, if we consider the same notion but with space considerations to get a class $X$, Is such a class known to be of any importance? Why?

To be more precise, $L\in X$ iff there exists a TM $M$ s.t.

$\forall x\in \{0,1\}^* (x\in L \iff  \exists u \in \{0,1\}^{p(n)}$ s.t. $M(x,u)=1$ s.t. $M$ uses space bounded by a polynomial $P$.

Clearly, NP$\subset$ X. Is there any interesting thing that we can know about $X$?


texts:
In Artificial Intelligence: A Modern Approach Edition 3, Page of 43, At Single Vs. Multi-agent section's last line, Writer says,

  In some competitive environments, randomized behavior is rational
  because it avoids the pitfalls of predictability.

Can someone help me understanding this line? Specially, what does he mean by pitfalls of predictability ?


texts:
Assuming $P\neq NP$, is it possible that there exists a $k$ such that $P\subseteq\textsf{NTIME}(t^k)$?

There reason I ask this is that I assume the following:
$$P=NP \implies \forall k\ \exists j.\ \textsf{NTIME}(t^k)\subseteq\textsf{DTIME}(t^j)$$ but I know that these statements are not exactly contrapositive to each other.


texts: Shortest path in graph by flipping binary colored nodes to one color

texts: Given a graph consists of two-colored nodes(e.g. white and black) and a starting node, and every time you visit a node, its color is switched(from black to white, or, white to black), how to find the minimum path such that all nodes are converted to black (or white, since it is equivalent)?


texts: Undecidable among these for turing machine

texts:
Below are two questions I found in Theory of Computation book but couldn't find its correct answers, can anyone please give correct answers with explanation?

It is undecidable, whether

an arbitrary Turing machine(TM) has 15 states
an arbitrary TM halts after 10 steps
an arbitrary TM ever prints a specific letter
an arbitrary TM accepts a string w in 5 steps

Which one of the following is not decidable?

given a TM M, a string s and an integer k, M accepts s with k steps
equivalence of two given TMs
language accepted by a given DFSA(Deterministic finite state automata) is nonempty
language accepted by a CFG(Context free grammar) is nonempty

Update: In first question I think 1.2 is right because halting is undecidable for Turing machine but not sure whether remaining options are decidable or not.
In second question I think 2 is right, but not sure about the decidability of non emptiness of CFG and DFSA.


texts: Is the language $K=\{u \in\{0,1\}^n\mid n \geq 0, \forall_{v \in\{0,1\}^n} (u+v) \in L \}$ regular?

texts:
For two words $w,v \in\{0,1\}^*$ of equal length, let $w+v \in\{0,1,2\}^*$ denote the word in which the $i$-th word is the sum of $i$-th position of $w$ and $v$, as follows: if $w=a_1 \ldots a_n$ and $v=b_1 \ldots b_n$, then $w+v=c_1 \ldots c_n$, where $c_i=a_i+b_i$ for each $i\in \{1, \ldots, n\}$.
Assume $L \subseteq \{0,1,2\}^*$ is a regular language. Decide whether the language $$K=\{u \in\{0,1\}^n\mid n \geq 0, \forall_{v \in\{0,1\}^n} (u+v) \in L \}$$ is regular.

I would appreciate any hint as I don't know how to start. I know that the every word u+v can be easily converted to be over the alphabet $\{0,1\}^*$ such that
$h(a_i) = 0$ if $a_i=0$ and $h(a_i) = 1$ if $a_i=1$ and
if $a_i = 2$, then $h(a_{i+1})=a_{i+1}+1$. Then $u+v$ is just binary addition.


texts: Hadamard transformation and measurement of one qubit

texts:
I also came across something, which is not completely understandable for me, so I ask here.

Given is a qubit in an entangled state, this is:
$$ \frac{1}{\sqrt{2}}(\left|00\right>-\left|11\right>) $$
Now it is said that one could also apply the Hadamard transformation to the first bit and measure the first bit of the pair.
That would mean so far:
$$ \frac{1}{\sqrt{2}}(\left|H(0)0\right>-\left|H(1)1\right>) $$
My question is, where does the measurement start now?

Do I have to measure H (0) and H (1) and if so how does that work?
For a single qubit, I know what a measurement looks like, say, we have
$$ \frac{1}{\sqrt{2}}(\left|0\right>-\left|1\right>) $$
Then my qubit is 50% in state 0 and 50% in state 1

But how is that applied to the entangled particle?

Alternatively, I've multiplied this step out
 $$ \frac{1}{\sqrt{2}}(\left|H(0)0\right>-\left|H(1)1\right>) $$
 $$ \frac{1}{2}(\left|00\right>-\left|01\right>+\left|10\right>+\left|11\right>) $$

Now my second question, what is the first bit of the entangled pair here?
and how is the probability that the first bit is in $ \left|0\right>$ calculated?

I hope you can help me a bit. Thank you!


texts: Undecidability of the language with its elements(TM) having empty language

texts:
We can write a decider for the language:

$E=\{A\; |\; A \mbox{ is a DFA and } L(A)=\emptyset\}$

by marking method. Why we cannot use the same method to write a decider for the language with TM as follows?

$A = \{ M \;|\; M \mbox{ is a TM and } L(M)=\emptyset\}$


texts: In how many steps Euclidean Algorithm will find the GCD for two integers

texts:
I'm trying to solve this problem for big numbers (up to $10^9$). Namely, let's define $$GCD(a,b) = GCD(a-b, b)$$

We define GCD as function that returns greates common divisor of two numbers.

In case if $b > a$ we swap the values of $b$ and $a$. Now I want to count the number of steps when either $a$ or $b$ will be equal to $0$.

Example

$$a = 4, b = 17\\GCD(17, 4) = GCD(4,13)\\GCD(13,4) = GCD(4, 9)\\GCD(9,4)=GCD(5,4)\\GCD(5,4) = GCD(4, 1)\\GCD(4,1) = GCD(1,3)\\GCD(3,1) = GCD(1,2)\\GCD(2,1) = GCD(1,1)\\GCD(1,1) == GCD(0,1)$$

We have total of 8 steps, however for big values those numbers are growing super fast.

What I tried

I know that this is solvable with Euclidean algorithm for finding GCD, but the faster variant of Euclidean variant is $GCD(a,b) = GCD(b, a \text{ mod } b)$, and for this variant the number of steps is less that $\log_{10}max(a,b)$. But for this variant the number of steps is big numbers, so I think that it can be only calculated with math steps.


texts: "Which complexity represents a majority of algorithms?"

texts:
Student asked me this question. During lectures on algorithm complexity I've shown similar picture (source):

After I've explained and gave examples for each category, a student asked: "Which of these represent a majority of algorithms?" I guess that the question is not right in a sense that we are creating new algorithms and that it depends on the field - majority of sorting algorithms are more complex than nlogn.

What would be your answer?

This question is only about the Big O as that was the end of the lecture.

Thanks!


texts:
People all over the internet are asking "What are the different Memory Mapping Techniques in Cache", but i couldn't find anywhere the answer to "What is Memory Mapping exactly?".

Please tell what do you mean by memory mapping?


texts: Optimal matching of individuals in vehicles

texts:
I am looking for an algorithm to find the optimal matching/allocation of n individuals in m identical vehicles. The aim is to create groups of individuals who will share these vehicles. Groups' size is bounded.

An individual i has incomplete preferences over the other individuals (some are not included into i's preference list when i can't share a vehicle with them).

I am looking for an algorithm returning a stable matching and minimizing the global cost for all individuals (cost for individual i being defined as the sum of the index of the individuals sharing i's vehicle in i's preference list).


texts: Can we derandomize subexponential algorithms given P=BPP?

texts:
Under $BPP=P$ conjecture randomization does not have much power for poly time algorithms.

Can we say the same about randomized subexp algorithms like number field sieve?


texts: Are all minimum spanning trees optimized for fairness?

texts:
I know by definition that a minimum spanning tree (MST) of a weighted, connected graph has the lowest global value for for sum of all edges in a path that connects all vertices.

I'm curious if all MSTs are also optimized for lowest individual edge value possible. (I know that ones calculated with Kruskal's Algorithm are!)

As an example, is it possible to have two MSTs in a graph (equal global sum of their edges) but have one of those MSTs contain an edge of higher value than any edge on the other MST in the graph.

Thanks for any help you can give!


texts: Is this variation of the assignment problem NP-hard, and does it have a name?

texts:
I’m trying to solve a problem very similar to the assignment problem, with a few twists.

The problem has a certain amount of workers, and a certain amount of tasks - workers is always >= tasks. Each agent has a cost to perform each task. The goal is to assign workers to tasks such that the total cost is minimized and so that every worker is assigned a task. However, there are far more workers than tasks, and multiple workers can be assigned to a task. A task has a “capacity” of how many people can be working on it. Thus far, what I have described can still be considered the assignment problem and the constraint of multiple workers to a task can be solved with the Hungarian Algorithm by cloning tasks to the amount of workers that can perform them at once. However, there’s one last constraint that breaks pretty much everything: workers have a type and only workers of the same type can work on the same task. Tasks do not have types, but the workers who work on them must all have the same type. I suspect this problem is NP-hard and has to be solved with probabilistic optimization algorithms.


texts: Forward Error Correction for streaming data

texts:
I am very familiar with error correcting codes. However, it is not obvious how to apply them to adaptive streaming data. There also doesn't seem to be much literature on the problem.

The naive approach might be to take small codewords of data and use forward error correction until there is a statistically significant chance that the client has received them. Then, move to the next codeword.

My question is whether there are known pitfalls with the naive approach and whether there exists a more comprehensive or performant solution (let's ignore the use of locally decodeable codes for now).


texts: Given two heuristic values how do I tell which one is admissible?

texts:
I am given 2 list of admissible values for a graph, and the graph with the real cost to each of the nodes.

Am I correct in thinking the way to see which one is admissible is add up all the values of the h(n) and compare it to the total real cost of the graph?

Example:

  h1 total = 681 h2 total = 732

  Total cost of graph = 704

Does this mean h1 is admissible as it doesn't overestimate?


texts: Why can useless states in TMs not be found by traversing the state graph?

texts:
Can anyone explain why can't we use a Turing machine's transition diagram?
For e.g.
The definition of a USELESSTM is as follow:

  A useless state in a TM is one that is never entered on any input string.

    USELESSTM = { ⟨ M, q⟩ ∣ q is a useless state in M }

I know this problem can be proved to be undecidable by reducing ETM to it, but I want to know why can't we do a breadth first search of the Turing machine's state diagram to find states that are unreachable. Then based on whether or not we found any unreachable states, we can say that there are or there are not any useless states.


texts: Is there a generally accepted name for creating types that select a subset of other types?

texts:
Tl;Dr;

Given:

type A = { int: foo, int: bar }
type B = select foo from A

What is the name of the typing relationship between A and B?
What is the name of the operation of deriving type B from type A?

Long Version

When we talk of subtyping in programming we typically think of it in terms of whether a new subtype B of a type A is able to substitute for A. However, when you think of it in terms of implementation what you are actually saying is that B can do everything that A can. Typically B does more. It might implement the interface and add new fields and methods of its own.
So despite 'sub' sounding like 'subset' the relationship is more like the subtype enriching the supertype.
We derive the subtype from the supertype. I'm curious about deriving a new type by selecting a subset instead.

Consider two structures:

A = { int: foo, int: bar }
B = { int: foo }

The fields of B are a subset of the fields of A.

Is there a proper name for this relationship?
I would say A includes B.

You could implement A by embedding an instance of B. As in:

C = { B, int: bar }

In a language like Go, C is the same as A. In other languages you need to reference B to get to foo. i.e. C.B.foo rather than C.foo

Another kind of subset relation is subranging. For instance limiting a integer to a range of 0-10.

Q = int
P = int[0..10]

P is a subset of Q as before. You can still say Q includes P.
subranges are a special case of refinement types.

The main language I can think of where creating subsets is central is SQL.
We could define B as:

B = select foo from A

So selection is probably a better term to use than "sub-setting"?
B is not a subtype of A is it cannot be used as a substitute for A.
A is a subtype of B because it can be.
So B is a supertype of A.
I think this misses the essential distinction that we are deriving B from A
rather than the other way around. i.e. the process has a direction:

B = f(A) , where f = selection and B is a supertype of A

vs

subtype = g(supertype), where g is derivation/inheritance.

We also have intersection types which combine two types by producing the subset they have in common. SQL does this with joins. Unification in prolog has a similar effect. Selection is via intersection with a second type. You could view selecting the fields as constructing a set of selectors and which is then intersected with the original set. I'm not sure this is the correct way to look at it though. selection and intersection are not the same. An intersection ignores fields that are not common a selection operation should treat that as an error.

There is also destructuring (assignment) as in:

let x = { 10, 1 }
{y, z} = x

But this has to do with values more than types and the isomorphism between a structure and a generic tuple.

My question is:

Is there a generally accepted name for this kind of 'selection'?
What would you call a type system supporting this kind of relationship?

Bonus discussion questions:

Why is 'selection' not more common in general purpose programming languages as opposed to query languages? Surely they complement each other well?
Are there any interesting languages supporting this? How successful is the feature? (linq is very successful in C# for example)


texts: how to bound the probability that quicksort takes greater than n lg n time?

texts:
I am working on exercise 12.4-5 of CLRS (Cormen et al, Intro to Algorithms 3rd ed)

  Consider RANDOMIZED-QUICKSORT operating on a sequence of n distinct input numbers. Prove that for any constant k > 0, all but O(1/nᵏ) of the n! input permutations yield an O(n lg n) running time.

By RANDOMIZED-QUICKSORT, they simply mean quicksort with the pivot randomly selected from interval being partitioned, as opposed to always being chosen as, say the last element or something.

A previous thread on this same question had a single answer, which consisted entirely of a dead link plus a working link that leads to a set of (in my opinion) poorly-written notes for an undergraduate class, that does not answer the question, only having a very brief discussion of a particular case of quicksort with n ≈ 20.

I'm not even sure how to rigorously pose the question; my best shot is this:

  Prove that for any k > 0, there exists positive constants a, b, and n₀ such that for all n > n₀, the probability that RANDOMIZED-QUICKSORT makes more than a n lg n comparisons is less than b /nᵏ:

A similar problem appears in Knuth's The Art of Computer Programming vol 3, Sorting and Searching, as problem 42 on page 137 (with some minor notational edits for clarity):

  For any real number c > 0, prove that the probability is less than exp(-c) that quicksort will make more than (c + 1)(n + 1)H comparisons when sorting random data, where H = 1 + 1/2 + 1/3 ... 1/n. (This upper bound is especially interesting when c is, say, nʰ, where h is small and positive).

The solution to this problem is given at the end of the book, and consists only of the following:

  This is a special case of a general theorem due to R. M. Karp, see JACM 41 (1994), 1136-1150, section 2.8. Significantly sharper asymptotic bounds for tails of the quicksort distributions have been obtained by McDiarmid and Hayward, J. Algorithms 21 (1996), 476-507.

I hunted down the Karp paper, and it indeed proves the result from the Knuth problem.

While CLRS seemingly refers to Knuth for a great deal of the former's material, it seems to be that the result that CLRS is asking us to prove is actually stronger than the result in the Knuth problem. In particular if we take the parameter c in Knuth's result to be any c(n) = ω(1), e.g. even something extremely slowly growing like c(n) = ln ln ln n, then the Karp result says that the probability is less than exp[-c(n)] that quicksort will make more than [c(n) + 1](n + 1)H comparisons. Since H = Θ(lg n), this number is Θ[c(n) n lg n], and since we have defined c(n) = ω(1), this number is ω[ n lg n ], with maximum generality. However, with the choice c(n) = ln ln ln n, the upper bound of the probability is exp[-c(n)] = 1 / ln ln n, which is a much weaker upper bound than what CLRS is asking for: less than O(1/nᵏ) for any constant k > 0.

My questions are the following: is my interpretation of the CLRS question (the quoted block above, immediately after I say "my best shot is this") correct? If not, what, specifically, is CLRS actually asking us to prove? Also, what is the relationship between the CLRS question and the Knuth question? Is the Knuth result weaker than the CLRS result? If so, does the  CLRS result draw on more recent published research than the 1994 Karp paper cited in Knuth's "answer"?

Also, some further relevant reading: the McDiarmid paper that Knuth's answer points to cites a 1991 paper by Rosler, who showed that

$$
\Pr\left[\left|\frac{Q_{n}}{E[Q_{n}]}-1\right|>\varepsilon\right]=O\left(\frac{1}{n^{k}}\right)
$$

where $Q_n$ is a random variable indicating the number of comparisons made by quicksort on an input of size $n$, $\varepsilon$ is a fixed constant, and $k$ is any positive real number. It seems likely that this is the source of the result asked for in the original CLRS problem, although the formulation of the probability in the above equation does not seem extremely obviously equivalent to the CLRS phrasing.


texts: How does squaring time complexity imply the same time complexity for multiplying different numbers? Isn't it the other way round?

texts:
Found this in solutions of a test as being true

If you can square an n-bit integer in time $O(n \,log \,n)$, then you can multiply two n-bit integers in time $O(n \, log \,n)$.

How does the above scenario apply for multiplying different numbers? Isn't it possible that squaring is a special operation since it is just 1 number? . I would see this making sense.

If you can multiply two n-bit integers in time $O(n \, log \,n)$, then you can square an n-bit integer in time $O(n \,log \,n)$.


texts: Map overlay, any algorithm for face updating step?

texts:
In chapter 2 of this book the map overlay algorithm, which takes as inputs two doubly connected edge lists, is explained. "Basically" a line intersection algorithm allows to update both the half edges records and the vertices records. After such step the detection of boundary cycles is applied, and later a graph is built, where each connected component represents a new face record. It is explained how to detect whether a boundary cycle is clockwise or not, but I'm not sure how an overall module that implements this part should work. Say I have a DCEL where the face records are not valid, but both the half-edges and the vertices are, do you know any detailed algorithm the actually build the graph? Even a pseudocode is fine.

I can understand how to implement the boundary cycles detection, I would iterate through the half-edges list, navigate through the "next" record, remove such record from the list and when I reach the initial half-edge I would go to the next half-edge of the list and repeat. I would put such sub list of half edges into another list so I would have a list of boundary cycles. I would also label each element of the boundary cycles list as "clock wise" or "anti-clockwise" based on the trick the book explains. Once I have such a list how do I figure out what boundary cycles are incident to the same face? In practice what's the test applied?


texts: Bubble Sort: Runtime complexity analysis line by line

texts:
I'm trying to analyze Bubble Sort runtime in a method similar to how to it's done in "Introduction to Algorithms 3rd Ed" (Cormen, Leiserson, Rivest, Stein) for Insertion Sort (shown below).  I haven't found a line by line analysis like the Intro to Algorithms line by line analysis of this algorithm online, but only multiplied summations of the outer and inner loops.
For each line of bubblesort(A), I have created the following times run. Appreciate any guidance if this analysis is correct or incorrect.  If incorrect, how it should be analyzed.  Also, I do not see the best case where $T(n) = n$ as it appears the inner loop always runs completely. Maybe this is for "optimized bubble" sort, which is not shown here?
Times for each line with constant run time $c_n$, where $n$ is the line number:
Line 1: $c_1 n$
Line 2: $c_2 \sum_{j=2}^n j $
Line 3: $c_3 \sum_{j=2}^n j - 1$
Line 4: $c_4 \sum_{j=2}^n j - 1$ Worst Case
$T(n) = c_1 n + c_2 (n(n+1)/2 - 1) + c_3 (n(n-1)/2) + c_4 (n(n-1)/2)$
$T(n) = c_1 n + c_2 (n^2/2) + c_2 (n/2) - c2 + c_3 (n^2/2) - c_3 (n/2) + c_4 (n^2/2) - c_4 (n/2)$
$T(n) = (c_2/2+c_3/2+c_4/2) n^2 + (c_1 + c_2/2+c_3/2+c_4/2) n  - c_2 $
$T(n) = an^2 + bn - c$


texts: Notions of computational hardness in terms of information flow?

texts:
If we consider polynomial-time (or log-space) computable reductions $<_p^m$ as  transformations between computational problems, then the following definitions of known complexity classes suggest the conservation of information under "efficient" transformations. Assuming $P\ne NP$, it seems that information flows only from easy problems to hard problems thorough efficient reductions.

$P=\{L| L<_p Horn3SAT, \bar L <_p Horn3SAT \}$

$NP=\{L| L<_p 3SAT \}$

$CoNP=\{L| \bar L<_p 3SAT \}$

$NPC=\{L| L<_p 3SAT, 3SAT<_p L \}$

$PC=\{L| L<_p Horn3SAT, Horn3SAT<_p L \}$

  Is there a notion of computational hardness in terms of information flow that explains this apparent asymmetry of information flow between natural computational problems?

I am aware of the theorem that $P=NP$ if and only if a sparse set is $NP$-complete. I'm looking for notions different than set sparsity.


texts: Dynamic programming, coming up with an algorithm

texts: I've been banging my head against the wall for the past two days and can't seem to come up with anything useful. The problem that needs to be solved is the following: I get an array of integers and I must return an array containing the elements that would give the maximum sum with the following condition: If I select an element, then I cannot use the one before or after it. I think I must, like it often is with dynamic programming, somehow order my results in a matrix, but I have no idea how to go about it. Any help is greatly appreciated.


texts: Under which field of computer science does cloud computing fit?

texts:
I am trying to categorise subfields of computer science. Wikipedia does a good job of it.

However, it cannot fit cloud computing, virtual machines, containers and related technologies in any of the mentioned fields.

Does it fit under computer architecture or do we need a new sub-field?

I know categorising topics under subfields might not seem that useful but it really helps me put things into perspective.


texts: Why are primitive types stored in a stack in systems level software?

texts:
Firstly 2 disclaimers, I am very new to the concept of a stack at a low level. I've only encountered it because I'm learning rust and the docs mention it. Secondly, I am aware of another similar question on this site, but it doesn't address a very specific concern.

My understanding of a stack is that it follows First In Last Off and cannot be searched, this confuses me if I do this.

variable a = 22;
variable b = 33;
variable c = 44;

Then my understanding is that c will be on top of the stack. So if I want to do something with a and b, will the system have to pop c and dig deeper for a and b? This seems inefficient. And an indexed array seems better.


texts: what will be the time complexity of below recursive algorithm

texts:
Please help me find the time-complexity of below recursive algo. I have guessed for first two return statements.Please correct me if I am wrong. But I can't find time-complexity of third return statement because it will loop till we get a factorial of NUM contining 0 and 7.

    public class Check
   {

   static long NUM = 11;
   public static void main(String[] args)
   {

       System.out.print(find007(NUM));
   }

     static long find007(long n){

       if(is007(n))  //O(1)
         return n;

       if(n+NUM<n)   //O(1)
         return 0;

       return find007(n+NUM);  //O(?)
     }
     static boolean is007(long n){
        while(n!=0 && (n%10==0 || n%10==7))  //O(log n)
         n=n/10;

       return n==0;
     }
}

Pseudo-code:

static long find007(long n){

 check if number or its multiple consists of only 0 or 7.
if yes, return the answer/number
 return n;

//if not, keep checking for the other multiples of NUM
i.e n+NUM (here NUM=11, so it will keep adding 11 to itself till 77)
   return find007(n+NUM);
}

 static boolean is007(long n){

   continue till n!=0 and  n%10==0 OR n%10==7
        n=n/10;

     return true if n==0;

         }


texts:
What would be the most space-efficient way to represent a multiset (a set that can contain duplicates) using a (static) bit string (bit vector, bit array, etc.)? All of the elements in the multiset would be integers from a limited range.

My current approach is to find the greatest frequency and allocate that number of bits to each element (i.e the multiset [0,1,1,2,3,3,3,3,4] becomes 1000 1100 1000 1111 1000), but this is rather inefficient.

For reference, the larger problem is that I want to securely calculate the intersection between two multisets, so I pretty much need each bit to correspond to an element. I also need two parties to be able to build a bit string where each bit corresponds to the same element without giving away much information in the process.


texts:
I need to come up with a data structure that supports the following interface:

new(time_stamp x, value v): insert a new data v for time stamp x
update(time_stamp x, value v): update the data for time stamp x to v
delete(time_stamp x): delete the data for time stamp x
query(time_stamp x): returns sum of all data whose time stamp is less than or equal to x

The data structure needs to support out of sequence data. I need the query operation to run in O(1) time. While there is no restriction for other provided interfaces, I don't want to end up with O(n) time complexity for any of them.

An AVL tree seems a good candidate, however I'm not aware of any technique (maybe amortized cost analysis) to reduce the O(log n) query complexity for AVL tree to O(1).

I appreciate any suggestion or direction toward implementing such a data structure.


texts:
I am currently studying the roofline model. Wikipedia [2] shows the following example graph:

The diagonal line shows $\beta * I$. But I do not understand why this line does not go through the zero point. If $I = 0$ so should $\beta * I = 0$. What am I misunderstanding here?
[2] https://en.wikipedia.org/wiki/Roofline_model


texts: Which is the fastest method for calculating exact square root of a integer of 200-500 digit number?

texts:
I wanted to know is there any algorithm / function / process through which I can calculate square root of a very large integer number. I wants to know current state of the research in this field.

No approximate methods please.


texts: What is this data structure/concept where a plot of points defines a partition to a space

texts:
I encountered an algorithm to solve a real world problem, and I remember a class I took where I made something very similar for some for a homework problem.

Basically it's a plot of points, and the lines are drawn to be equidistant between two points. It forms a perfect partition where the lines around the point form the shape of area that is closest to that point. Does this ring a bell to anyone? I've had a tough time googling descriptions and getting results. And I don't know how else to describe it. Hopefully the picture helps.


texts: Greedy algorithm correctness proof for "Elegant Permuted Sum" (UVa 11158)

texts:
Given a sequence of $2 \leq n \leq 50$ numbers $s = (s_1,s_2,...,s_n)$, find a permutation $a = (a_1,a_2,...,a_n)$ of $s$ such that $$\sum_{i=1}^{n-1} |a_i - a_{i+1}|$$ is maximized.

I found many codes that get "Accepted" in the online judge with the following greedy algorithm.

  If $n = 2$, then $a = s$. Stop the algorithm.

  Let $s' = (s'_1,s'_2,...,s'_n)$ be $s$ in the non decreasing order.
  Start the optimal sequence with $a = (s'_1,s'_n)$ and remove these two
  elements from $s'$.

  $\text{loop}$: Let $s' = (s'_1,s'_2,...,s'_k)$ be the remaining sorted
  sequence. If $k = 0$, stop the algorithm. If $k > 0$, from the
  following choices, choose the one that yields the greatest absolute
  difference.

  Remove $s'_1$ from $s'$ and push it to the front of $a$.
  Remove $s'_1$ from $s'$ and push it to the back of $a$.
  Remove $s'_k$ from $s'$ and push it to the front of $a$.
  Remove $s'_k$ from $s'$ and push it to the back of $a$.

  Go to $\text{loop}$.

I'm having trouble to formally prove the correctness of this algorithm.

For example, to prove the optimal substructure property. Let $b = (b_1,b_2,...,b_n)$ be an optimal solution. How can I argue that $(b_1,b_2,...,b_{n-1})$ is also optimal? What if it's not???

And for proving the greedy-choice property. Let $a = (a_1,a_2,...,a_m)$ be a partial, yet still optimal, solution. The algorithm relies on the fact that only adding $s'_1$ or $s'_k$ to $a$ can yield another optimal solution. Why is this true? And more, why we don't need to test inner positions for inserting the new element, but only the ends?

Any help with these proofs? Or, perhaps, this algorithm is not correct? But I can't find a counterexample...


texts:
Are there two function $f:N\rightarrow N$, and   $g:N\rightarrow N$ such that $f(n)+g(n)\ne O(f(n))$ $\wedge$ $f(n)+g(n)\ne O(g(n))$?
My idea:  i think because of for any $f:N\rightarrow N$, and   $g:N\rightarrow N$ then $f(n)+g(n)= O(\max \{f(n),g(n)\})$ then there are no two such functions.
is my argument is valid?


texts: Build a histogram from a very large data sample

texts:
I want to calculate a histogram from an array of size N. N is very large.

I know 2 ways to do so:

The naive approach is to find the maximum and the minimum in the first traverse and to split the range into equal bin ranges then to fill bins during the second traverse. However this approach produces degenerate histograms where most of data is piled in one bin if the sample has outliers.
The way to counter degenerate histograms is to calculate IRQ or MAD, then calculate range based on this robust measure of scale, and then fill bins in one traverse. However calculation of IRQ or MAD may be slow and requires random access to the array.

I'm intrested if there is a way to build a histogram in between this extreme approaches fulfilling conditions:

some loss of quality is acceptable
the array doesn't fit in RAM so random access is the thing I want to avoid
low time complexity, i'm ready to trade space ~log(N) for time


texts: Does input space size contribute at all to the runtime of an algorithm?

texts:
I just started learning about NP-Complete problems and one of the first examples they give is Set Cover:

  Given a set $U$ of $n$ elements, a collection $S_1, \ldots, S_m$ of subsets of $U$, and a number $k$, does there exist a collection of at least $k$ of these sets with the property that not two of them intersect?

This is I'm sure a very basic question, but I was wondering whether the amount of space in $n$ the input takes up matters at all in the formulation of runtime. This is the first example of an algorithm I've seen where the input itself takes up space exponential in $n$ since of course there are $2^n$ possible subsets of $U$. Thus, it seems that possibly the time needed to allocate the space necessary to even "handle" the input prevents there from being a polynomial time algorithm.

Or rather, do we just assume that the input magically appears in our hands already allocated before we start keeping track of algorithm runtime? And as a side question, can we choose what data structure it is given to us in? This seems more natural to me, but I wanted to make sure. I know, for example, that the time needed to allocate an output (or allocate anything in between) does matter.


texts:
Today I learned about an abstract class of machines called linear bounded automata.

It is intended to model real-world computers that have a limited amount of memory. I have always thought that real computers are DFAs due to the finite memory (but the DFA is a terribly poor abstraction).

Is it possible to convert LBA into an equivalent DFA by making every possible tape configuration into a state of the DFA?


texts: Proof that there is a recursive language that is not decidable in $O(n)$ time

texts:
I having some trouble tackling an assignment. We're asked to prove that there exists a recursive language that's not decidable by a Turing machine in $O(n)$ time for inputs of length $n$. We're supposed to do so using diagonalization.

Here's what I have so far:

Assume that for each recursive language $L$, there exists a TM that decides $L$ in $O(n)$ time for each input of length $n$.

We build a TM, $U$, that for each input, $w$, $U$ interprets $w$ as $ w = 1^k0\langle M\rangle$,
where $\langle M\rangle$ is an encoding of a TM for language recognition. It
then runs $M$ on $w$, and if $M$ halts, then $U$ outputs the opposite of $M$'s output. Therefore,$ U$ must perform at least $k$ steps in order to extract the encoding of $M$ from the input. I'm still not sure how to continue from here.


texts:
There are $n$ items with weights $w_1,\ldots,w_n$ and values $v_1,\ldots,v_n$. There is a knapsack with capacity $W$. A subset of items is called feasible up to heaviest item if, once the heaviest item is removed from the subset, the weight of the remaining set is at most $W$. The knapsack up to heaviest item problem is to find a subset that maximizes the total value subject to being feasible up to one item.

I was trying to solve this problem, and I think I found that it is NP-hard - by reduction to standard knapsack problem. Given a standard knapsack problem, construct a knapsack-up-to-heaviest-item problem as follows.

There are $n+1$ items: the $n$ items in the original problem, plus one "big item".
The big item has value $v_B > \sum_{i=1}^n v_i$ and weight $w_B > \sum_{i=1}^n w_i$.
The size of the new knapsack is $W+w_B$.

In the new problem, any optimal solution must contain the big item, since if it does not contain the big item, the sum of weights in the knapsack is less than $W+w_B$, so the big item can be added and the solution is still feasible.  Moreover, in any optimal solution, the heaviest item is the big item. Hence, once the big item is in the knapsack, the problem is equivalent to the original knapsack problem.

My questions:

Has this problems been studied before?
Is my hardness proof correct?


texts: How to apply insights from the theory of codes to alternating codes?

texts:
The book Theory of codes by J. Berstel and D. Perrin from 1985 studies variable-length codes. The focus is less on error-correction and compression, but more on algebraic properties, synchronization and connections to automata (especially unambiguous transducers). A code over a finite alphabet $A$ is any subset $X$ of the free monoid $A^*$ generated by $A$ which satisfies:

  If $x_1\dots x_n=y_1\dots y_m$ with $x_i,y_j\in X$, then $n=m$ and $x_t =y_t$ for $t=1,...,n$,

or equivalently, any subset $X$ of $A^*$ which is of the form $h(B)$, where $h: B^* \to A^*$ is an injective morphism (and $B$ need not be finite).

A key insight for me was that codes in this sense are well behaved under composition, and that a suitable automaton (for a prefix code, a deterministic automaton is suitable) can decode such a code without delay, i.e. each symbol can be decoded as soon as its complete code has been transmitted, no need to wait for the beginning of the code for the next symbol.

However, this nice theory fails to capture codes like the Morse code, where a long pause is used to separate individual codes. Separators somehow don't fit into the given framework:

  You probably agree that there is no block code which can encode all integers. So we could use a prefix code to encode integers. But then a deterministic machine is no longer able to read the numbers backwards. We could use a separator, which actually works, but somehow doesn’t fit into the framework of (pure) codes (for whatever reason).

One idea to force separators into the given framework is to consider alternating codes. Alternating codes are used for example in fax encoding of BW images, where the run-lengths of black and while pixels alternate, and are encoded by two different codes, because the statistical distributions of run-lengths for black and while pixels are different.

A general question concerns the need for this long introduction: The writing style of J. Berstel, D. Perrin and C. Reutenauer is fine for me, but the length and depth of their presentations makes them less suitable for a cursory introduction to the subject, and hence also less suitable as a place to link to for the basic definitions and concepts. Is there a nice introduction to this subject online that I could link to instead? (I linked to the review of their book instead of the book itself, because the review at least tries to give definitions of some basic concepts.)

I tried several definitions of alternating codes, and guess that the following definition should work fine: An alternating code over a finite alphabet $A$ is any pair of subsets $(X,Y)$ of $A^*$ such that $XY$ has no duplicate elements (as multiset) and is a code over $A$. Here "should work fine" means that I hope the following to be true:

A pair of subsets $(X,Y)$ of $A^*$ is an alternating code iff $(Y,X)$ is an alternating code.
If $(X,Y)$ is an alternating code and $Y$ is a prefix code, then $XY$ is a prefix code.

Is it true? Is there a better definition of alternating codes? (One issue is the behavior under composition. I wonder how to force separators into the given framework without degrading the behavior under composition.)


texts: Cases where string concatenation is commutative

texts:
Strings are known to not satisfy the commutative property.
pq is not equal qp unless p is empty string. Is there a case where pq can be qp where both are non empty strings and p and q are distinct


texts: How can I optimise this bitmask generation algorithm?

texts:
I am emulating the left shifting of a 128-bit integer using two 64-bit integers. For this I must calculate the bits that need to be moved into the higher portion. I have the following algorithm for generating a bitmask that masks the last until bits.

Where until is an integer in the range 0..64:

 ~(power(2,64-until))-1)

For convenience this is it in Python:

def mask(until): bin((~(2**(64-until)-1))&0xFFFFFFFFFFFFFFFF)

Is there a faster way to do the same thing by avoiding the costly use of power()? Or is this the most efficient way?


texts: How to convert pixel relative focal lengths to mm.

texts:
Ive been playing around with the Intel Realsense R200 Camera.
I am able to exact focal length in x and y i.e. fx and fy,
but only "up to scale relative to pixel width and height, respectively"

At the moment I dont see any way of querying the pixel dimensions in mm from the API nor can I find them in the tech specs.

So my question is: How can I get the fx and fy in mm?
One way I can think of is to take a picture of my checkerboard pattern and count the number of pixels and divide by the size in mm.

Is there a better/more elegant way? It seems kind of..imprecise.

Best,
Marc


texts: What does Online Transfer Learning Mean?

texts:
The last sentence of A review on transfer learning in EEG signal analysis states that:

Furthermore, online learning needs to be developed to ensure the
performance of transfer learning in practical applications.

Can someone explain to me online transfer learning?
What is mostly not clear to me is where the new labels are coming from.
How should I imagine it?


texts: Proving correctness of inefficient algorithm - Path between two vertices

texts:
Consider the following inefficient algorithm that decides if there is a path between two vertices s and t of a directed graph G. Show that the algorithm is correct. In addition, analyze its complexity and compare it with the other path between two vertices algorithms (Dijsktra, Bellman-Ford Algorithm, etc.) and explain why this algorithm is inefficient.

ALGORITHM Reachable(G, s, t)
     RETURN A(G,s,t,|V(G)|)
END Reachable

FUNCTION A(G,s,t,d)
     IF d=1 THEN
        IF s == t OR there is a directed edge (s,t) in G THEN
              RETURN TRUE
        ELSE
              RETURN FALSE
     ELSE
          FOR each vertex v in G DO
              IF A(G,s,v,d/2) AND A(G,v,t,d/2) THEN
                   RETURN TRUE
              ENDIF
          ENDFOR
          return FALSE
END A

I tried to prove correctness using invariants, but I'm not sure if that's the best way to prove it. Could you help me, please?

And I tried to obtain time complexity considering the for-loop, but also I have doubts.

Thanks a lot for your help!


texts:
$$ (\neg A \wedge \neg C) \vee (\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C) $$
can simplify down to
$$ (\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C) $$
I've computed the truth tables for the two expressions, and they're the same. But I'm supposed to prove it without using truth tables. What law(s) am I supposed to use?


texts: Can someone let me know if my understanding of amortized run time in a dynamic array list is correct?

texts:
Am I right in my understanding for amortized time for insertion in a dynamic array list? (dynamic means create a copy double its size and copy existing elements to new one WHEN we reach the current size limit). Please validate my explanation/understanding.

If we insert X elements into an array of initial size 0, it will perform the double/copy operation only at insertion number 1,2,4,8,16,..,X where each operation costs a function of X f1(X), f2(X), etc.

all other insertion operations like 3,5,6,7,9,10,11, etc is O(1).

the function of X which I mentioned above is because f1(X) + f2(X) +..+ fi(X) = 2X. where i is the number of double/copy insertions.

Hence, total execution time is O(2X+j.O(1)) where j is the number of easy operations. (3,5,6,7, etc) THIS is the part I want to verify if my understanding is right or not

therefore, total time is O(2X) = O(X)

but since we are looking for the time of only inserting one element, it is O(X) / X = O(1)

hence amortized time is O(1)

Last question: why is it called amortized? Where did I amortize anything?

Thank you!!


texts: What's the worst case complexity of Robert W. Floyd's cycle detection algorithm?

texts:
Givens. I understand Floyd's algorithm can determine the length $\lambda$ of the loop and the length $m$ of the tail.  The hare will not necessarily catch the tortoise on the first cycle, but it is guaranteed to catch it after a number $k$ of cycles, where $k$ is a natural number.

Question. Given I know these facts, how can I deduce the worst case complexity of the algorithm?

An answer that seems fallacious.  For the tortoise and the hare to meet, they both need to be in the cycle.  This will occur certainly after $\mu + \lambda$ iterations.  Once the tortoise is in the cycle, the distance between the tortoise and the hare diminishes by one at each iteration.  Yuval Filmus' answer shows that they meet in the cycle in an index that's a multiple of $\lambda$.  Therefore, after they're both in the cycle, after $\lambda$ iterations (in the worst case) they must have reduced their distance to zero --- because the largest distance between them in the cycle is $\lambda$.  But how do I know the hare didn't jump the tortoise?  This argument doesn't seem very good.


texts: Whenever CPU needs the data, it gives the address of that word to the RAM via bus, then the RAM generated the copy of that word and sends to the registers via bus. Why can't the RAM send the original data instead of the copied data? Are there any disadvantages of storing original data or reference in registers?


texts: Mathematics topics or fields that increase computer programming proficiency?

texts:
Generally computer programmers who are mathematicians or have mathematics background are very good in terms of algorithms and computer programming in general.

What I am not saying:

Mathematics is needed to be a good computer programmer.
Mathematics is necessary for programming.
Good mathematicians are good programmers and vice versa

What I am saying

I would like to learn some mathematics because I believe it will make me a better programmer. What areas/topics of mathematics will help me to become a better programmer? Answers of the form math topic - corresponding cs area will be appreciated.

NB: I asked this on StackOverflow where it was declared off-topic. I want to learn it during my spare time just the way I have been doing with computer programming. Thanks in advance.


texts:
I want design algorithm that allows a student to take important courses quickly up until graduation. no time, room number,  professors needed here. just my selected courses I know will allow me to graduate but how best to take them based on prerequisites. the student can decide how many courses to take a semester. And, you cant take a course's prerequisite and itself
eg cs101 cs102 201 but cs201 cant be taken in the first semester because i have to take its prerequisites first. Additionally prequisites can be  such that 101 and 102 or 101 and 104 are possible choices to take as prerequisites to a course 201. We could also have 101 or 106 and 102 or 105 ossible choices to take as prerequisites to a course 202.

any suggestions and how to go about it. Trees, graph adjacency list

I was thinking topological sort will give a valid ordering but i think i would ran into trouble when placing them in across semesters because topological sort order them linearly eg cs101 cs102 201 but cs201 cant be taken in the first semester because i have to take its prerequisites first. And what about if we have cs 103 cs104 cs202. cs103 and 104 have nothing to do with cs101 102


texts:
we have to run a song on a Walkman,for that we need 2 full batteries.Let s say we have a mixed set of 30 batteries (15 are emtpy and and 15 are full)
and then only way to test if the battery full or empty is to put them in the Walkman and try it out.we can not tell which one is empty or full (one we put inside one full and one empty).

The question is to find the maxmium needed step to run the walkman (to find 2 full batteries)

I modelled the problem like that :
let s that the Walkman is a function f which take two argumments and it return 1 it the walkman works ,and 0 otherwise.
$$ f: \{b_1,b_2 \dots b_{30}\} \times \{b_1,b_2 \dots b_{30}\} \rightarrow\{0,1\}$$

The answer for the question was at most 18 steps , but somehow i could not figure it out.
Any  good suggestion how to proceed ?


texts: Dijkstra algorithm step in Introduction to Algorithms

texts: In the introduction to algorithms proof of Dijkstra, I don't understand why the statement "both y and u were in V-S when u was chosen". We add x before y, and so we relax d[y] with the the edge $$\omega(<x,y>) + \delta(s,x)$$, d[u] can't be smaller than delta[u], so shouldn't y be in S when we add x to S? thanks.


texts: What is the big-$O$ notation of a summation of a log?

texts:
For:
$$\sum^{n+m}_{i=n} \log(i)$$
I'm wondering what the big O notation is and how to prove it...
I believe that we can also write this as
$$\log(n) + \log(n+1) + \log(n + 2) + \ldots + \log(n+m)$$

also $$\log(n+m)!/\log(n-1)!$$

Thanks


texts:
I have a question regarding counting DFAs:

  Given a  Σ = {0, 1} input string, with the state set Q = {1...n}, how would I find the total number of DFAs that can be constructed?

I believe this is a combinatorics problem, but I am not really sure what I would have to multiply.

Thanks.


texts: Recursive function calculating number of ways to sum $a + 2 b + 3 c = x$

texts:
Using python need to code a recursive function with one input and no global integers that calculates the number of options to get $x$ using $a*1+b*2+c*3$.

Say $x=3$, there are four options: $\lbrace (1,1,1),(1,2),(2,1),(3)\rbrace$.


texts: Combination with a minimum number of elements in a fixed length subset

texts:
I have been searching for long but unable to find a solution for this. My question is "Suppose you have n street lights(cannot be moved) and if you get any m from them then it should have atleast k working.Now in how many ways can this be done"

This seems to be a combination problem, but the problem here is "m" must be sequential.

Eg: 1 2 3 4 5 6 7 (Street lamps)
Let m=3
Then the valid sets are,
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7

Whereas, 1 2 4 and so are invalid selections.

So every set must have atleast 2 working lights. I have figured how to find the minimum lamps required to satisfy the condition but how can I find the number of ways in it can be done ?

There should certainly some formula to do this but I am unable to find it.. :(

Eg: Let n=7,m=4,k=3. The minimum number of lights that must be working to satisfy the condition that "atleast 3 of any 4 lights must be working" is 5. It is if 23467 are working. But there are more ways in which it can be satisfied like if 23467,13457... We have 4 such combinations in all for the taken values of n,m,k. I want to know how can we generalize this?

Can be represented like this :
n => 1111111
1 Indicates light working and 0 indicated not working.
0111110
0111011
1011101
1011110

Hope the question is clear.


texts: Can there still be infinite recursion if I remove all left recursion?

texts:
I have to transform the following grammar into a non left recursive grammar:

S →  aSb | bAS

A →  AaA | bAA | AAa | bAb

This is what I came up with:

A → bAAA’| bAbA’

A’ → aAA’| AaA’| ε

S →  aSb | bAS

As far as I can tell, there is no more left recursion because none of the leftmost symbols on the RHS are the same as the nonterminal on the left. However, assuming S is the starting symbol, there is still infinite recursion because A calls itself repeatedly. Is this expected? Or did I derive the non left recursive grammar incorrectly?


texts: RDT2.1 - does the Sender listener to "ack" even though state=ready?

texts:
Computer Networking:
  A Top Down Approach
  Featuring the Internet,
  Jim Kurose, Keith Ross
  Addison-Wesley 4nd edition , page -223.

Also here slide 60 .

RDT2.1 (Reliable data transfer) -

Sender(s):
state=ready; i=0;
On rdt_send(d,m):
    if state=ready
    then
    { p=<s,d,m,i,
    EDC(s||d||m||i)>;
    udt_send(p);
    state=busy; }
On udt_deliver(a)
     If a=<“ack”,EDC(“ack”)>
    then
    { i++;
    state=ready; }
    else udt_send(p);

When the Sender side is in state=ready , does he still listener to "ack" recived from the Reciver ?

I need to know this , cause if so it seems that the Sender can get duplicate "ack"'s from the reciver and inc the i without sending any packet mainwhile .


texts: How to treat ϵ-productions in table-driven predictive parsing?

texts:
Here:
https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html
in chapter Driver Procedure, it's shown how table-drive predictive parsing works.

The predict table however can involve $\epsilon$-productions (which leads to including a production in the symbols of $FOLLOW(w)$, where $w$ is a non-terminal/row, in addition to $FIRST(w)$) and I cannot find how these should be treated. I.e. how should the parser decide whether it predicts for an $\epsilon$-production or non- $\epsilon$-production. I.e. e.g. how should the end of the string be handled by the Driver.

Case example:

Such production involving the $\epsilon$ could be e.g.

$$A \rightarrow \text{B | c | $\epsilon$}$$ where c is a terminal and B is a non-terminal.

The remaining input could be "". So how should the driver decide to match with the $\epsilon$ and not e.g. something that the non-terminal $B$ leads to.

A guess would be that it tries all of the symbols between the $|$s but fails in other than the $\epsilon$.


texts: What is the regular expression describing this language?

texts:
The language is $\{w \mid \text{$w$ is any string except $11$ and $111$}\}$ where the alphabet is $\{0,1\}$.

Drawing the DFA recognizing $\{v \mid \text{$v$ is either $11$ or $111$}\}$, then switching the accept and non-accept states, and finally examining this resulting structure, I thought of it as being:

$(ϵ∪0Σ^*∪1∪10Σ^*∪110Σ^*∪111Σ^+)$

My reasoning was that it has to accept the empty string,
or a 0 followed by whatever
or just a $1$
or, if it begins with a $1$, a $10$ followed by whatever
or, if it begins with $11$, then a $110$ followed by whatever
or a $111$ followed by at least a $0$ or a $1$

Does this appear to be correct? If I'm wrong, could you please tell me why?

Thank you,


texts: Finding maximum subgraph with vertices of degree at most k

texts:
Let $G = (V, E)$ be an undirected graph and $U \subseteq V$ some subset
of its vertices.  An induced graph $G[U]$ is graph created from $G$ by
removing all vertices that are not part of the set $U$.
I want to find a polynomial time algorithm that has graph $G = (V, E)$
and integer $k$ as input and returns a maximum set $U \subseteq V$ with
largest size such that all vertices of $G[U]$ have degree at most $k$.
My idea with greedy algorithm that removes vertices with largest degree
or vertices connected with most vertices with degree greater than $k$
doesn't work.
Does anyone know how to solve this problem in polynomial time?


texts:
This is a question I have stumbled upon in my textbook, and didn't really know how to approach:

Given a $k$-bit binary counter.
We have an operation Increment, which adds 1 to the counter.
We add a new operation Decrement, which subtracts 1 from the counter.
Prove that the cost for executing $n$ operations is $\Theta(nk)$.


texts:
In bioinformatics they study biological data. I have seen codes dealing with DNA sequences. However, they are treated as string literal. I was wondering if there were data structures or classes in OOP sense ( even partial representation) for RNA and DNA.

Any help would be greatly appreciated.

CS


texts: Extending ordered tree edit distance to DAGs

texts:
Computing edit distance (shortest sequence of edit operations) on ordered trees is a well studied problem with many known algorithms (e.g. Zhang & Shasha, RTED). There is also considerable literature on edit distance for general graph (e.g., this review). I am however interested in a mixed case that has arisen in our inquiries into RNA structures in computational biology: how to compute edit distance between directed acyclic graphs (DAGs) with ordered children, i.e. a DAG where each node imposes a total ordering on its outgoing edges. There seem to be multiple ways to define edit operations on such "ordered DAG" but as a first approximation, I don't care about which edit operations are primitive. I was unable to find any literature on this problem.

Is there a known algorithm for edit distance on ordered DAGs (or more general graphs with ordered outgoing edges)? Or can some of the known tree edit distance algorithms be easily extended to cover DAGs?

Note that I cannot defer to algorithms for general graph edit distance as those (AFAIK) don't take order of outgoing edges into account.


texts: Why does not valiant's reduction show NP=RP?

texts:
Valiant converts $SAT$ formula to a $0/1$ matrix such that $Permanent$ of the matrix is $4^m\#SAT$.

We know $Permanent$ can be approximated to $1+\epsilon$ factor with probability $1-\frac1\delta$ in time $poly(m|\epsilon|^{-1}\log\frac1\delta)$.

Why does not these two help me tell when number of witnesses to $SAT$ formula is $0$ in randomized polynomial time?

What do I miss?


texts: Genetic algorithms, Pittsburg - Reach a decision from a set of rules

texts:
Consider a binary classification problem. In the Pittsburg approach each member of the population represents a set of rules. Each rule encodes information regarding the data features (that is, the conditions of the if rule) and information about the class (that is, the conclusion or then part in the if rule).

Then in principle the same member can learn a couple or more rules that are in contradiction for the same example from the data. For instance, for a certain member that has learnt Rule 1 and Rule 2 the following may happen: Rule 1 would classify an example as belonging to class A, and rule 2 would classify the same example as belonging the class B.

How does a member reach its final decision (class A or B) when it can have rules reaching different conclusions?


texts: What is the shortest superstring for $\{c (ab)^k, (ba)^k, (ab)^k c\}$?

texts:
In this paper on PDF page 3, they give $\{c (ab)^k, (ba)^k, (ab)^k c\}$ as an example of an input to the GREEDY algorithm for shortest superstring that causes it to have an approximation ratio of 2.

As far as I can tell, the shortest superstring of that set is either $c (ab)^k c (ba)^k$ or $b (ab)^k c (ab)^k$ -- either way, the length is $4k + 2$. Unfortunately, this contradicts the claim in the paper that GREEDY outputs a string of length 2 times the optimal superstring.

Without loss of generality, we can assume that GREEDY will never output a string longer than the concatenation of its input set -- if the GREEDY algorithm really is described in that way, we can just add an if statement to check that case and return the concatenation instead.
The length of the concatenation of the input strings is $6k + 2$.
For all $k \in \mathbb{N}$, $1 \le \frac{6k + 2}{4k + 2} \le 1.5$
Therefore either the approximation ratio for any reasonable algorithm on this class of problems must be less than or equal to 1.5, or what I think is the shortest superstring is not actually the shortest one.

Can someone either explain why this line of argumentation doesn't work, or say what the actual shortest superstring of this set is?


texts: Time complexity of insertion in binary search tree

texts:
Given a binary search tree $T$, we insert $n$  elements, but when the size of tree become doubled then we balance the tree. for example if we insert $2^{k-1}$ element then when the size become to $2^k$ then we balance $T$. what is time complexity insert $n$ items in such tree?
I think be $O(n)$, but when i want draw a such tree i get stuck.


texts:
So i understand how to use radix-sort in base 10 and utilize mod 10 to go through the numbers. But not sure about 2,8 or 16.

Does it follow the same idea? and i read somewhere that i need to pass the base number to the radix function but not sure why would that be needed? because if i have for example:

int arr[] = {0xAA, 0x2D , 0x4B, 0x5A, 0x322, 0x24, 0x2, 0x42};

it works perfectly. So not sure why i need to pass the base to the function.


texts:
I have a theory that all finite state machines can be monitored by a second turing machine with infinite tape to determine if the state of the first machine was repeated thus reaching the conclusion that the finite state machine must be looping. I'm fairly confident that this is not a new idea but I could not find anything relevant through all my searches and reading here. Knowing that all modern digital computer hardware has finite RAM and local storage, we can make the statement that all modern digital computers are equivalent to an arbitrary large FSM.
for example, a program that outputs all the non-negative integers {0,1,2,...}
this program will never halt if it is run on a turing machine with infinite tape. however, this program would eventually overflow and rollover to 0 on a machine with finite ram. assuming that an overflow does not halt. this machine also does not halt. however, the implementation with finite RAM can be monitored by another turing machine that records a copy of the contents of RAM in a new dictionary file on the second turing machine with infinite tape. you could in theory then run a program on the second machine that checks if any new state exists in the dictionary. if it exists in the dictionary then output a warning message that the FSM is looping. I believe the implication of this conclusion is that the halting problem must have a turing machine with infinite tape as a requirement for the halting problem to remain undecidable. This is equivalent to the statement that any modern computer hardware can in theory have a watchdog process that monitors a sandbox that has allocated a very small limited RAM for repeating patterns to confirm that a program is in fact undecidable. an example of this is hardware PRNG which always loops and the period can be determined by another process on the same machine. Is there a name for this conjecture?


texts: Fast computing of a matrix power for large integer values in C++

texts:
I'm working with squared matrices that can be quite large, for instance, a M = 50 x 50 matrix.
My objective is to compute the power of the squared matrix M^t for very large t values (for example t = 4000).
I work in R and I have used the R function matrix.power from the matrixcalc R package.
I'm exploring the possibility to write a code for matrix power in C++ and then import it in R through the R package Rcpp.
One alternative would be to use the matrix multiplication approach (as in the matrix.power function in R), but looking around I have understood that there might be faster approaches to calculate a matrix power.
Do you have any experience on that? Does anyone know a library in C++ that does matrix power calculation fast and efficiently?
Consider that I'm working on a Mac0s laptop with 16 GB of RAM and 4 CPUs.


texts:
I am trying to implement the algorithm described in the paper A quantum-inspired classical algorithm for
recommendation systems.

This is the algorithm:

These are the necessary definitions for mathematical notations used in the algorithm to understand the algorithm.

  The distribution is defined as, for a nonzero vector $x \in R^n$, we
  denote by  $\mathrm{D}_x$ the distribution over [1, ..., n] whose
  probability density function is $$\mathrm{D}_x(i) =\frac{x^{2}_{i}}{\lVert{x}\rVert ^2} $$.

  If a matrix $A \in R^{m \times n}$, and let $A_i$  refer to the $i$th
  row of $A$. Let $\tilde{A} \in R^m$ be a vector whose $i$th entry is
  $\lVert A_i \rVert$.

  $[p] denotes [1, 2, ... p]$

  $s \sim _u [p]$ denotes pulling an $s$ uniformly at random.

I am having a problem understanding the Let the resulting p x p submatrix ... step of the algorithm. According to the algorithm the rows of the submatrix are sampled from a distribution $\mathrm{D}_{\tilde{A}}$ and the columns of the submatrix are sampled from a distribution $\mathcal{F}$.

I can't understand how can we form a submatrix with both rows and
colums given ? I think we just need either rows or columns. Can someone clarify
this to me, please ?
And I also don't understand the definition of $\mathcal{F}$.
According to definition of $\mathcal{D}_x$, $x$ has to be a vector
then how can we choose a column from $D_ \tilde{A_{i_s}}$.


texts: Why does the formula floor((i-1)/2) find the parent node in a binary heap?

texts:
I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the index of the parent of element at index i can be found with
parent index = floor((i-1)/2)
I have tried to explain why it works. Can anyone help me verify this?
Took reference from Why does the formula 2n + 1 find the child node in a binary heap? thanks to @Giulio


texts:
I was trying to rule out whether this was LL(1) by checking for left-recursion in the following grammar:

$\qquad  A \to 0 A 1 \mid 0 1$

Which produces:

$\qquad 0 A 1 \Rightarrow 0 0 A 1 1 \Rightarrow \dots$

But I am unsure what type of recursion this is called, since it sorta stays in the middle.

If this is not left-recursive, would you agree that this is not LL(1) because non-terminal A has 0 appear twice in FIRST(A)?


texts: Converting (reverse-engineering) Turing machine into program or most concise algorithm?

texts:
It is known that every program or every algorithm can be converted to Turing machine. But what about the reverse process? Is there algorithm (or research trend that considers such algorithm) to convert some Turing machine into algorithm as expressed in some high level programming language (e.g. in Algol, Java, Prolog, Haskell)? The comprehensiveness/conciseness or such resulting algorithm can be defined as one having the minimal number of aggregated operations or the minimal length of the program code or the minimal number of variables or the minimal number of states (if one considers the operational semantics of the resulting program)?

I can imagine that several ways can be followed (I am not expert in any of the mentioned fields, so, theses are only musings that may have been already discovered but with such names that I can not Google them):

On can convert Turing machine to lambda expressions and them do some kind of term rewriting of them.
On can convert Turing machine to its operational semantics expressions, do transformations in the semantics domain and then extract the software code from the transformed semantics.

This question can be extended more broadly - take some low level code (e.g. lot of Prolog like rules) and extract concise algorithm from them.

The mentioned problem constantly arises int the decoding process or neural networks. There are efforts to extract set of rules from the neural networks. So - how to convert this large set of rules into concise algorithm? There are efforts to extract deterministic finite automaton from the neural network that accepts or rejects the strings that belong or don't belong to some simple language. So - why bound us with DFA? We should consider full Turing machine and try to convert it into algorithm. This problem should be solved if we are required to create explainable neural networks.

Of course, I am aware about code optimization and program analysis, but I feel that this question is far beyond that.

This question has some similarity with reverse engineering of assembler programs, maybe it can be good staring point as well?


texts:
This may be an elementary question, but I'm new to circuit complexity.  Does 2-SAT in CNF form belong to the complexity class AC$^0$?

It seems simple enough to construct an AC$^0$ circuit of depth 2 of polynomial size for 2-SAT. $~$Given $n$ variables (which means $2n$ literals), there can be at most $\frac{(2n)(2n-1)}{2} = n(2n-1)$ number of OR gates at Level one, because, given $2n$ literals, there can be at most $n(2n-1)$ clauses.  At Level 2, there is just one gate (an AND gate).

But we can also extend this to 3-SAT.  $~$The only difference is that at Level one, the maximum number of OR gates would now be ($2n$ choose $3$), which is $O(n^3)$, still polynomial in the number of variables.  Doesn't this mean that 3-SAT is also a member of AC$^0$?  Wouldn't this mean that 3-SAT is polynomially solvable?  What am I doing wrong?


texts: Why do we consider the order of growth when analyzing algorithms?

texts: Seriously why do we consider how the computation time time increase  with the number of inputs as a measure of performance when we can easily measure such as program execution time,power consumption,memory usage etc?Because all of these facts are depends on the hardware and programming language we use in that moment and order growth is only depends on inputs?


texts: What are the drawbacks of using an algorithm that is not backwards stable?

texts:
(This question might be legitimately crossposted to stackoverflow or mathoverflow or programming StackExchanges.)

Preface

I'm reading this paper on solving linear systems of equations Ax = b using an explicit inverse (held by conventional wisdom as a big no-no): Druinsky & Toledo, "How accurate is inv(A)*b?", http://arxiv.org/abs/1201.6035

It asserts that in non-pathological cases, calculating a solution to Ax=b via inv(A)*b using the explicit inverse of a matrix produces solutions that are as accurate and as stable as preferred methods such as via LU factorization. It goes on to describe exactly which situations using "inv" might be bad (technically, when the right-hand side, b, is nearly orthogonal to the subspace spanned by left-singular vectors of A with low singular values). Even in these cases, the paper asserts, the solutions of inv(A)*b are as accurate as preferred methods, they're just not backwards stable.

Question

My question is: what are the specific drawbacks of using an algorithm that isn't guaranteed to be backwards stable? If all I wanted was some solutions to Ax=b, and I was guaranteed accurate results, does it matter that the solutions aren't backwards stable? Is there any specific examples of when it's ok to use an accurate but backwards-unstable algorithm?

Furthermore

My experimentation in Matlab/Octave shows me that the difference between a backwards-unstable and -stable algorithm is that slight perturbations to the solution result in bigger errors when going back through the linear system:

norm(A * (inv(A) * b) - b)

is much larger than

norm(A * (A \ b) - b)

for a "bad" b (nearly orthogonal to the subspace of left-singular vectors with low singular values), where \ solves linear systems using Gaussian elimination (http://www.mathworks.com/help/matlab/ref/mldivide.html). The solutions themselves have the same accuracy, i.e., norm(A\b - true_x) is about the same as norm(inv(A)*b - true_x).

I can imagine that in the case that

I only cared about getting a solution to Ax=b and
knew I would never propagate the solution back through A,

could I justify using inv(A) when I didn't want to bother checking that b isn't "bad", i.e., without ensuring that the solution was backwards-stable. To me, this doesn't seem worth it, even without the speed and convenience advantages of using LU or Cholesky or QR decompositions.


texts: Can quick sort time complexity be $\Theta(n\sqrt n)$ for some inputs?

texts: I know that the time complexity of quick sort in the worst case is $\Theta(n^2)$ and in the average case is $\Theta(n \log n)$. Can it be $\Theta(n\sqrt n)$ for certain inputs?


texts: Find the sum of the first K subsets of integer array

texts:
We have given a multiset of $N$ integer, both positive or negative. Consider  all $2^N$ subsets, sorted by their sum (the empty subset has sum 0). We want an algorithm that outputs only the first $K$ sums.

The problem is that $N$ can be very big number (up to 100000), so we cannot generate all subsets. How to optimize the search so we wont generate more than $K$ subsets.

$K$ in the problem will also be up to 100000.

I was thinking to get the smallest possible subset and then try to make it bigger and bigger, but I couldn't come to something that will work in all cases.

The problem is from past csacademy contest:
https://csacademy.com/contest/round-79/task/smallest-subsets/


texts: why are deterministic PDAs not closed under concatenation?

texts:
I can understand that they are not closed under concatenation because without non determinism, PDA cannot decide whether to loop in the first PDA or jump to the next one.
But can someone prove this with an example. Also prove that the resulting language cannot be accepted by DPDA


texts:
I have a set $S$ of integers.  I want to remove all elements of $S$ that are divisors of another element of $S$.  In other words, I want to compute $T = \{y \in S : \forall d \in S . d \nmid y \}$.

How do I do this efficiently?

I can see how to do it in $\Theta(|S|^2)$ time, by examining all pairs of elements of $S$ and keeping only the ones that don't have any divisor in $S$.  Can it be done substantially faster?  (For simplicity, I'm willing to assume that all standard integer operations---addition, multiplication, division, etc.---can be done in $O(1)$ time.  Yes, I know this is an imperfect approximation, but if it makes your answer cleaner, I'm fine with it.)


texts: In the reduction from HALT to ALLHALT, why does the constructed Turing machine loop indefinitely when the inputted Turing machine rejects?

texts:
Let HALT be the language $\{\langle M, w\rangle : M\text{ is a TM that halts on }w \}$. Let ALLHALT be the language $\{\langle M\rangle : M\text{ is a TM that halts on all inputs}\}$. Use a reduction from HALT to show that ALLHALT is not decidable.

Online (link) I found this (simular) solution:

  $D$ = on input $s$:

  Check that $s$ is of the form $\langle M, w\rangle$, where $M$ is a Turing machine and $w$ is a string over the input alphabet of $M$. If not, reject $s$.
  Otherwise continue.
  Define a new machine $M_2$ corresponding to the pair $M, w$ as follows.

  $M_2$ = on input $v$:

  If $v$ is not the same as $w$, halt. Otherwise continue.
  Feed $v$ (meaning $w$ in this case) to $M$ and let $M$ compute on $w$.
  If $M$'s computation on input $w$ halts and rejects $w$, loop
  indefinitely. If $M$'s computation on input $w$ halts and accepts $w$,
  halt. Otherwise continue looping like $M$ is doing.

  Notice that we've designed $M_2$ in a clever way so that the result of
  $M$'s computation on input $w$ is encoded in the halting behavior of $M_2$.
  Namely, $M$ accepts $w$ if and only if $M_2$ halts on all inputs. In terms of
  language membership, this means that $\langle M, w\rangle$ belongs to Halt if and only if $\langle M_2\rangle$ belongs to Halt2. In light of this fact, finish the description of $D$'s computation as follows.

  Feed the string $\langle M_2\rangle$ into the decider $D_2$.
  Return $D_2$'s decision.

I don't understad the point 3: If $M$'s computation on input $w$ halts and rejects $w$, loop indefinitely. Why does $M_2$ need to loop indefinitely?


texts:
Looking for a book that describes the path the code takes from high-level to compiler to memory etc.

Doesn't matter which programming language is used, just would really like a nice breakdown of the steps the computer takes to execute it in thorough detail.

Thanks!


texts: On efficiency analysis of randomized divide-and-conquer median find

texts:
I read following explanation from Dasgupta's Algorithms book for Median finding, this is the same philosophy applied in randomized quick-sort.
Here as per book terminology $S$ denotes array of integers, $v$ is pivot, $S_{L}$ and $S_{R}$ are left and right side of pivot element.
To distinguish between lucky and unlucky choices of $v$, we will call $v$ good if it lies within the 25th to 75th percentile of the array that it is chosen from. We like these choices of $v$ because they ensure that the sub lists $S_{L}$ and $S_{R}$ have size at most three-fourths that of $S$ (do you see why?), so that the array shrinks substantially. Fortunately, good $v$’s are abundant:
half the elements of any list must fall between the 25th to 75th percentile!
In one of the interview it was asked to me up till what range this median finding gives average running time of $n$.
i.e. Favourable range of selection is within 25 to 75 percentile. But up to what extent we can reduce this and still have average running time of $n$
My approach was to write recurrence relation and then from the height of the tree comment on average running time, but I doubt is it a correct way to have answer? Also it might not provide tighter bounds.
It will be helpful if someone can also suggest what mathematical tool/technique will be useful for this kind of analysis.


texts: Parall execution of algorithms that solves polynomically disjoint subsets each of a NP-hard problem

texts:
I was thinking in the following approach for solving a problem that is believe to be a NP-hard problems today in polynomial time, assuming the following:

There exists a believed-today NP-hard problem called $X$, where its whole input space can be divided into a finite set of groups such that there exists a corresponding "single-threaded" polynomial-time algorithm for each group (that only runs polynomically for the inputs corresponding to its designated group, without any complexity guarantees regarding inputs for other groups).

Since we don't neccesarily have a criteria to know, polynomically, to which group a certain input belongs to, a possible approach to solve such problem $X$ polynomically is to run all algorithms in parallel and wait for the first that finishes, aborting the execution of everyone else.
Since we have at least one polynomial-time algorithm for every possible input of $X$ (because of the conditions given above), and we are executing all algorithms at once, such problem will be solved in polynomial time for every input, and so every believed-today NP-hard problem can be solved polynomically previous transformation to an instance of $X$.
Is there any research in this direction?


texts: Prove that every CFL is decidable in O(n) space

texts:
this question came up while a group of students at my school were studying for our qualifying exams. The question on an old exam was:

  Prove that every context free language $A$ is in $\mathrm{SPACE}(n)$. You can assume that $A$ is given in CNF (Chomsky Normal Form)

I saw CYK algorithm but it's space complexity is $O(n^2)$.


texts: Prove that the total distance is minimised (when travelling across the longest path)

texts:
Here is the problem: Given a tree $T$, I need to visit every node in the tree once. I can start and end anywhere I want. I would like to travel the least distance possible when doing so. I don't have to return where I started.

As my specification is not really clear I made up an example: Consider the graph (which is a tree here - undirected weighted acyclic graph) to have nodes as cities and edges as roads between cities. I need to deliver something to every city (visit every node at least once). I can start from any city and end at any city that I choose to.

I read the following result. Find the two cities in the graph that are the farthest apart (call them $c1$ and $c2$). Start from one of them ($c1$ or $c2$), visit every other city along the way until I reach ($c2$ or $c1$). This minimises the total distance to travel.

How should I prove that this is the minimum distance ?

I attempted the following. I have the final route and I call edges, $m_1, m_2, ..., m_i$ and $e_1, e_2, ..., e_j$. Where $m_1, m_2, ..., m_i$ are the edges along the cities that are the farthest apart ($c1$ and $c2$) and $e_1, e_2, ..., e_j$ are everything else in the graph. As I start from $c1$, I travel along edges labelled m exactly once and everything else labelled e is a digression and go back and forth twice on those edges, before I reach $c2$.

We know that $m_1, m_2, ..., m_i$ and $e_1, e_2, ..., e_j$ taken together include all the edges on the graph (as it is a tree, there's only a unique path between every two nodes). So the distance I travel could be given as $2(e_1 + e_2 + .... + e_j) + (m_1 + m_2 + ... + m_i)$.

I need to prove that this sum is less than every other route that I can take to reach all the cities. My intuition says that this has to be the shortest route. I feel that have to use the fact that $(m_1 + m_2 + ... + m_i)$ is the maximum between any two nodes in the graph somehow (is that called the diameter ?), and arrive at a contradiction.

This is the kind of picture I have in my mind (red edges are in ($m_1, m_2, ..., m_i$) and the grey ones are everything else),

That graph is still a tree (please ignore the arrow head in the edges that show how I decide to travel). I don't to where to go from here. I would appreciate a proof that is simple to understand (This is not a homework or anything related to coursework.)


texts: Random variate generation in Type-2 computability

texts:
Is there any existing literature on applying the theory of Type-2 computability to the generation of random variates? By "random variate generator" I mean a computable function $f\colon\subseteq\{0,1\}^{\omega}\rightarrow D$ such that, if $p$ is a random draw from the standard (Cantor) measure on $\Sigma^{\omega}$, then $f(p)$ is a random draw from a desired probability distribution on $D$. Think of $f$ as having access to an infinite stream of random bits it can use in generating its output value. Note that $f$ need not be a total function, as long as its domain has (Cantor) measure 1.

It seems to me that the way to proceed would be to require that one specify a topology on $D$, in fact a computable topological space [1] $\boldsymbol{S}=(D, \sigma, \nu)$ where $\sigma$ is a countable subbase of the topology and $\nu$ is a notation for $\sigma$, and use the standard representation $\delta_{\boldsymbol{S}}$ of $\boldsymbol{S}$. One might also want membership in the atomic properties $A\in\sigma$ to be "almost surely" decidable; that is, there is some computable $g_A\colon\subseteq\{0,1\}^{\omega}\rightarrow\{0,1\}$ whose domain has measure 1, such that

$$g_A(p) = 1 \mbox{ iff } f(p)\in A$$

whenever $p\in\mathrm{dom}(g_A)$.

I'm working on a problem that needs a concept like this, and I'd rather not reinvent the wheel if this is a concept that has already been well explored.

[1] See Definition 3.2.1 on p. 63 of Weihrauch, K. (2000), Computable Analysis: An Introduction.


texts: Amortised analysis of a simple loop and 3 operations

texts:
I'm trying to figure out amortised analysis of this loop and I can't figure out how to prove that complexity is $O(n \log n)$.

Operation OP(S,X[i]) has complexity O(log|S|) and operations push and pop has constant complexity O(1).

S <- Emptystack
for i=1 to n do
    while (S!=0) and OP(S,X[i]) do
        pop(S)
    od
    push(S,X[i])
od

I would like to proove it using potential function. It would be simple if there were just pop(S) and push(s):

Pot.function represents number of items in stack

  C^ PUSH = 1 + |S|+1 - |S| = 2

  C^ POP = 1 + |S|-1 - |S| = 0

So the complexity would be linear (O(2n)) = O(n). But I don't know how to compute amortized complexity of OP.


texts: The abstract interpretation corresponding to the pure simply typed lambda calculus

texts:
In Types as Abstract Interpretation, Patrick Cousot sketched how different type systems could be constructed from the collecting semantics of a language. However, the notation of the paper is very old and I'm not able to reconstruct it.

Does anybody see what would be an abstract interpretation corresponding to the simply typed lambda calculus as described in for instance figure 9-1 of the TAPL book?


texts: Computational complexity based in the input size

texts:
In an answer to a previous question Luke Mathieson wrote:

  A place where this might fall down is when you are working with numbers. As a number with magnitude $m$ can be encoded in $n=O(\log m)$ bits, if our running time were $O(m)$, this would be $O(2^n)$ - exponential in the actual input size - which would make the magnitude $m$ a bad choice for a proxy for the input size if we wanted to talk about membership in $\mathcal{P}$ for example (when you come to Strongly-$\mathcal{NP}$-complete and Weakly-$\mathcal{NP}$-complete, remember this). On the other hand, if all we were interested in was decidability, then it would be a good enough proxy measure.

Can you explain to me how if the running time is $O(m)$ goes to $O(2^n)$?


texts:
Suppose I have a simple dependent type theory with bottom, unit, sums, dependent pairs, dependent functions, natural numbers and homogeneous identity with J-elimination.

Is there a way to prove $(0 = 1) \rightarrow \bot$? Or do I need K for that?


texts: Finding suitable NP-complete problem to reduce to my problem

texts:
I've been given a set $S$ of natural numbers (non-negative integers) $s_1$, $s_2$,...,$s_n$ where $|S|=n$. My problem is to figure out if there is way to get a total sum of 0 when using all the numbers of $S$ but we get to "choose the sign" for each number: that is, for $s_i$ we get to choose if we're going to add or subtract $s_i$ from the total sum.

I've tried visualizing it using a directed cyclic graph with $n$ vertices where the only edges from $v_1$ to $v_2$ are $+/- s_1$ and the task is to traverse the whole graph, ultimately getting back to our starting node $v_1$ using a path with total weight 0.

What would be a suitable NP-complete problem to reduce into this one?


texts: How to properly solve T(n) = T(n-1) + O(2^n)?

texts:
I've been trying to solve this recurrence: T(n) = T(n-1) + O(2^n)

My approach when writing everything out and solving the geometric series was: T(n) = O(2^n).

T(n) = c2^n * (1 + 1/2 + 1/4 + ...)

= c2^n * (1/2)^i for i from 0 to infinity

T(n) <= d*2^n for some constant d.


texts: Finding all paths between a set of vertices in a DAG

texts:
Given a  graph G= (V, E) that is:

directed,
acyclic,
non-weighted,
may have more than one edge between two vertices (thus, source and destination are not enough to determine an edge).

And given a set of vertices, let's  call them vSet; that contains a vertex vRoot; I need to find ALL paths pSet between vSet elements respecting the following:

any vertex that appears as a source for some path in pSet must be reachable from vRoot.
any path in pSet must has its source and destination from vSet, and must not contain any other vertex of vSet.

I've developed an algorithm similar to BFS, that starts from vRoot (according to 1 above),  grow each of the current paths with one edge per an iteration until it reaches another vertex v1 of vSet; then store this reaching path and start growing new set of paths staring from v1.

Here is a pseudo code

output = ∅;
maxLengthPaths = ∅;
1. add all edges that vRoot is there source to maxLengthPaths
2. while size(maxlengthpaths) != ∅ do
  (a) paths := ∅;
  (b) extendedPaths := ∅;
  (c) foreach path p in maxLengthPaths do
    i. if (destination of p in vSet)
      1. add p to output
      2. for each edge e that destination of p is its source
        A. add e to extendedPaths
    ii. else
      1. add p to paths
    iii. for path p1 in paths
      1. for each edge that destination of p1  is its source
        A. extend p1 by a edge and add it to extendedPaths
  (d) maxLengthPaths = extendedPaths

Here are my questions:
1. Is this the best way to achieve my task?
2. I was trying to figure out its time complexity; I found that its exponential of pow(maxNumberOfOutGoingEdgesFormAVertex, maxLengthPath). Is this really the complexity?


texts:
My similarity search seminar topic are M-trees. I would like to give some examples about where they are practically applied, but I can't find anything googling.

Does someone know if M-trees are still used and what for? I am interested in answers regarding both practice and applied research.


texts: Minimize the DFA(Deterministic finite Automata) given in the picture

texts: How to minimize the DFA given in the picture


texts: Why the update low value in Tarjan's for the ancestors is not it's low value instead of it's discovery value?

texts: In Tarjan's algorithm for finding SCC/AP/Bridges, we update the value of the low[u] to be the min ( low[u], desc[v] ) given that v is a neighbor and has been discovered before, why it's not like this instead low[u] = min(low[u], low[v])?


texts: Minimum pumping length of concatenation of two languages

texts:
there's this small part of my homework that I just can't figure out.

Let us denote $p(L)$ as the minimum pumping length of some language $L$. I'm supposed to find two regular languages $A,B$ so that

$$
p(AB)=p(A)+p(B)
$$

But whatever I try, I can only find languages so that

$$
p(AB) < p(A)+p(B)
$$

I've been sitting at this the whole day and I'm just going in circles. Can someone please give me a hint?


texts:
I have two binaries, $\alpha_{ts,it}$ and $\alpha_{ts,gshp} \in \{0,1\} $, and two reals $T_{it}$ and $T_{ts}$ which have upper and lower bounds. How can I model $\alpha_{ts,it}=1$ if the following constraints are met:

$T_{ts}\geqslant-7$
$T_{it}\leqslant14$
$T_{ts}-T_{it}\geqslant5$
$\alpha_{ts,gshp}=0$

Regards

SR89


texts: Time complexity of combinations of n pairs of parentheses

texts:
I have the following code snippet for combinations of n pairs of parentheses.

def parens(n):
    if n <= 0:
        return ['']
    else:
        combinations = []
        helper('', n, n, combinations)
        return combinations

def helper(string, left, right, combinations):
    if left <= 0 and right <= 0:
        combinations.append(string)
    else:
        if left > 0:
            helper(string + '(', left - 1, right, combinations)
        if right > left and right > 0:
            helper(string + ')', left, right - 1, combinations)

What's the reasonable estimation of the time complexity of it?

My trials:

(2n)!/n!n! since it's permutations of multisets with more limitations.
Resolve recurrence: T(n) = 2T(n-1) => O(2^n).


texts: Counting inversion pairs - $n^2$ results in $n \log n$ time?

texts: The number of possible inversions in an array is bounded by $\binom{n}{2}$, i.e $\frac{n(n-1)}{2} \in O(n^2)$. How it is possible to calculate $O(n^2)$ results in $O(n\log n)$ time using something like modified merge sort? (sample algo : http://www.geeksforgeeks.org/counting-inversions/).


texts:
It is said that practically all-zeros and all-ones subnets are not used.

Let us consider an a network $200.200.13.13/25$

Here Network ID is represented by using $25$ bits and Host ID using $32-25=7$ bits.

Binary Representation : $11001000.11001000.00001101.00000000$

Last 7 bits which represent HID are $0000000$

Suppose we want to divide the network into $4$ subnets, so we will borrow $2$ bits from Host.

So the subnets will be

$11001000.11001000.00001101.00000000$ - $200.200.0.0/27$

$11001000.11001000.00001101.01000000$ - $200.200.0.64/27$

$11001000.11001000.00001101.10000000$ - $200.200.0.128/27$

$11001000.11001000.00001101.11000000$ - $200.200.0.192/27$

Now it is said that all-zeros and all-ones subnets are not used, then let us consider -

(i) the IP addresses ranging from $200.200.0.0 - 200.200.0.63$ which should belong to all-zeros subnet and

(ii) the IP addresses ranging from $200.200.0.192 - 200.200.0.255$ which should belong to all-ones subnet

Will belong to which subnet/network or will remain unallocated ?


texts: Can every algorithm's running time be expressed as $\Theta(f(n))$?

texts: That is, can the running time of every algorithm $A$ be written as $O(f_A(n))$ and $\Omega(f_A(n))$, for the same function $f_A$?


texts: Find longest path in graph with N nodes and N edges

texts:
We have given weighted undirected connected graph with $n$ nodes and $n$ edges, we want to find the longest path in it. Note that the path should be in each node at most once. Since the graph has $n$ edges clearly it has exactly 1 cycle, and removing 1 edge from this cycle will lead us to a tree.

Clearly we can iterate over all edges of the cycle and run dijkstra to find this path in tree. But this has complexity of $O(N^2)$ in worse case if the whole graph is cycle. I was thinking that greedy solution that we should remove always the edge with lowest weight that lies on the cycle. How to prove this greedy solution, is it correct at all?


texts: Calculate the number of combinations of a sequence of numbers in a particular order

texts:
I have a problem solving coding challenge when I have to calculate the number of combinations, numbers from 0 to 9, with the length n, with 2 rules -

- The first number cannot be 0

- Every other number can be 0 or must be divisible by the previous number (number 1 can not be used as divisor), for example [5.0], [1,0] or [2,8], [4,8], [3,6]

For example, if the length n were 2, number of combinations would be 23 - [1,0]...[9,0] + [2,4], [2,6], [2,8], [3,6], [3,9], [4,8] + [2,2]...[9,9]

The resulting response can be code in some programming language or a formula to calculate answer