Can both $f(n) \neq O(g(n))$ and $g(n) \neq O(f(n))$ happen at once? For which case are both $f(n) \ne O(g(n))$ and $g(n) \ne O(f(n))$ true?

I have following answer to this which I could not understand:

  Sometimes true: For $f(n) = 1$ and $g(n) = |n \sin n|$ it is true, while for any $f(n) = O(g(n))$, e.g. $f(n) = g(n) = 1$, it is not true.

Please someone help in understanding:

For which case is it sometimes true? An explanation with example will be much appreciated.
What is meaning of "||" in this?

Consider the following statement about two functions $f,g$:

  $f(n) \neq O(g(n))$ and $g(n) \neq O(f(n))$.

The question wants you to choose which of the following holds:

The statement holds for every $f,g$.
The statement holds for no $f,g$.
The statement holds for some $f,g$, and doesn't hold for other $f,g$.

The third option is correct in your case, and this is the meaning of "sometimes true".

Indeed, if $f(n) = g(n) = 1$ then the statement doesn't hold. Conversely, if $f(n) = 1$ and $g(n) = |n\sin n|$ (where $\left|\cdot\right|$ denotes absolute value) then the statement does hold.


Number of bits needed to represent an integer with a specifed base How many bits are required to represent an integer $ x $ with base $b$?

You could, if you wanted, encode each digit of the base $b$ representation of an integer in $\lceil \log_2 b \rceil$ bits. This was actually done in the very early days of computing, when binary-coded decimal (BCD) encoding was used to store each digit of the decimal representation of an integer in four bits, from $0000$ for $0$ to $1001$ for $9$.

This somewhat simplifies user input and output (as long as your users always want to work in decimal). The downside is that it makes internal arithmetic more complex, and it wastes memory space. In BCD encoding one byte ($8$ bits) of memory can only store an integer between $0$ and $99$, whereas in binary encoding it can store any integer between $0$ and $255$.

All modern computers store integers internally in binary and do all their internal arithmetic in binary, and convert from or to other bases in their input and output as necessary.


Example request for Monotone 1 in 3 SAT I know that monotone 3SAT is NPComplete. Also, 1 in 3SAT is NPComplete. I think  both conditions together also leave the problem NP Complete (need confirmation).

If possible can someone please help with the smallest non trivial problem of this form that is unsatisfiable. Would be grateful.

How about $(x_1 \lor x_2 \lor x_3) \land (\bar{x}_1 \lor \bar{x}_2 \lor \bar{x}_3)$?


How to show that this problem is NP-hard: Find two subsets of 2 given sets such that the difference between the subset sums is $\leq v$ As input, given two finite sets of integers $X = \{x_1,...,x_m\}$, $Y = \{y_1,...,y_n\} \subseteq Z$, and a non-negative integer $v ≥ 0$. The goal is to decide if there are non-empty subsets $S ⊆ [m]$ and $T ⊆ [n]$ such that
$$ \left|\sum_{i\in S}x_i-\sum_{j\in T} y_j\right| \leq v$$
How to show this problem is NP-hard? I'm quite confused.
What I got so far is to reduce from subset sum problems, since the form is set to less than v.  So I need to have 2v+1 subset sum problems to verify

The special case where $v=0$  and $Y=\{\frac12\sum_{i=1}^m x_i\}$ is the partition problem, which is NP-complete.


Computing probability of sentence using N-grams I have implemented N-grams by constructing a tree (or a trie, technically) that stores frequencies of each N-gram. Each path in the tree represents an N-gram and its frequency: the path consists of N nodes (each node containing a word), followed by a leaf node containing the frequency. So, each path in the tree is of length N + 1.

I'm now trying to compute the probability of observing a given sentence, and am having some trouble, particularly when N > 2.

For the sentence <s> Hello world </s> using N = 1, the probability is P(<s>) * P(Hello) * P(world) * P(</s>).

Using N = 2, the probability is P(Hello | <s>) * P(world | Hello) * P(</s> | world).

But for N = 3, I'm not sure what to do. If I compute P(Hello | <s>) * P(world | <s> Hello), then my tree will give an error since <s> Hello is a bigram and the tree is only defined for trigrams.

I considered maybe wrapping each sentence an additional time, e.g. <s> <s> Hello world </s> </s> then computing P(Hello | <s> <s>) * P(world | <s> Hello) * P(</s> | Hello world) * P(</s> | world </s>), but this seems non-intuitive and involves mutating the corpus in an ugly way.

What is the proper way to compute this probability?

The $N$-gram model assumes a generative model in which the next word generated depends only on the preceding $N-1$ words. Using Bayes' law, we get that the probability of a sentence $w_1,\ldots,w_n$ is
$$
P(w_1\cdots w_n) = P(w_1) P(w_2|w_1) P(w_3|w_1w_2) \cdots P(w_N|w_1\ldots w_{N-1}) P(w_{N+1}|w_2\ldots w_N) \cdots P(w_n | w_{n-N+1}\ldots w_{n-1}).
$$
In the particular cases $N=1,2,3$, this gives
$$
P(w_1\cdots w_n) = P(w_1) P(w_2) \cdots P(w_n), \\
P(w_1\cdots w_n) = P(w_1) P(w_2|w_1) P(w_3|w_2) \cdots P(w_n|w_{n-1}), \\
P(w_1\cdots w_n) = P(w_1) P(w_2|w_1) P(w_3|w_1w_2) P(w_4|w_2w_3) \cdots P(w_n|w_{n-2}w_{n-1}).
$$
This means that your expression for $N=2$ is wrong.

In practice, we don't want to store special tables for the first $N-1$ characters. There are two ways around this. First, we can ignore entirely the first $N-1$ words. This makes sense when the text is very long, and we don't expect the first few words to make a big difference in the resulting probability. Second, we can include a special "blank" symbol and add it to our tables, so that (for example) $P(w_1)$ is stored as $P(w_1|\not{b}\ldots \not{b})$.

Usually one stores not the actual probabilities but rather their logarithm. The reason is that adding numbers is faster than multiplying them. As an added benefit, you don't have to worry about the dynamic range of the floating point data type you use (the actual probability could be rather close to 0 and could cause underflow, but this is unlikely for its logarithm).

Another thing to keep in mind is that the results are more meaningful as the text becomes longer. Your example is very short and doesn't serve as a good test case.


Compute 'insertable' letters in a regular language Let $L$ a regular language and define the subsequence closure of $L$ as

$\qquad \displaystyle S(L) = \{ w \mid \exists w' \in L.\ w \text{ subsequence of } w'\}$.

The problem I want to solve is to find for such subsequences $w \in S(L)$ which letters can be inserted into them so that the result is also in $S(L)$. Formally:

  Given $w_1\dots w_n \in S(L)$, output all pairs $(i,a) \in \{0,\dots,n\} \times \Sigma$ for which $w_1 \dots w_{i} a w_{i+1} \dots w_n \in S(L)$.

Consider, for instance, the language$\{ab, abc, abcc\}$. The string $b$ is in $S(L)$ and inserting $a$ at the beginning -- corresponding to $(0,a)$ -- yields $ab \in S(L)$. On the other hand, the string $cb$ is not in $S(L)$; there is no way to convert it to a language string by insertion.

Using this language, if the input string is $b$ the possible insertions I am looking for are $(0,a)$ and $(1,c)$ at the end. If the input string is $bc$ the possible insertions are $(0,a), (1,c)$ and $(2,c)$.

The use of this algorithm is in a user interface: the user builds strings belonging to the language starting from an empty string and adding one character at a time in different positions. At each step the UI prompts the user with all the possible valid letters in all the possible insertion positions.

I have a working naive algorithm that involves a lot of back-tracking, and it is way too slow even in relatively simple cases. I was wondering if there is something better, or -- failing that -- if there are any available studies of this problem.

Edit: The OP changed the question. What follows works for one interpretation of the original question.

I'm assuming you are given a DFA $A = (Q,\Sigma,\delta,q_0,F)$. The method can be adapted to handle NFAs.

Let the word be $w = w_1 \ldots w_n$. For each $i \in \{0,\ldots,n\}$, calculate the state $s_i$ that the automaton reaches after reading the prefix of length $i$ of $w$. For each $i \in \{0,\ldots,n\}$ and each accepting state $q \in F$, calculate the state $t_{i,q}$ that the reverse automaton reaches when starting at $q$ and reading the reverse of the suffix of length $i$ of $w$. Let $T_i = \{ t_{i,q} : q \in Q \}$.

For each $i \in \{0,\ldots,n\}$ and each symbol $a \in \Sigma$, check whether $\delta(s_i,a) \in T_{n-i}$. If so, $a$ can be inserted at position $i$: $w_1 \ldots w_i a w_{i+1} \ldots w_n \in L(A)$.

The running time is $O(n(|\Sigma| + |Q|))$, and the method requires space $O(|Q|)$ (if implemented by going over $i = 0,\ldots,n$, in this order).


Map data structure terminology I'm looking for the correct terminology in regard to map (dictionary) data structure.
When I'm talking about the semantics of the values stored in map in the direction from keys to values, I'd say, for example

messages keys are mapped to message strings

When I'm using the opposite direction - describing the values first, I'd need to say something like

message strings are ??? by message keys ("being mapped by" just doesn't feel right here)

How about "message strings are associated with keys"?


Understanding 2's complement multiplication using Booth's algorithm I was referring Booth's algorithm for 2's complement multiplication from William Stallings book. It was explained as follows (please ignore two starting words "As before", it still makes complete sense):

The author then gives following example for $7\times 3$, which I am able to understand:

Next author gives examples for all combinations of +ve and -ve combination of multiplication:

Doubt

I am not able to get how example in figure 9.13 maps to same example but more compact approach illustrated in figure 9.14(a). I mean how those entries are made in fig 9.14 (a)

PS: Wanted to add tags "booths-algorithm" and "2s-complement-multiplication", but wasnt able to create those due to low reputations.

So, it goes like this, we have Q = 0011 and Q-1 = 0 in the beginning.
At the start, we have

count = 4(Q0 Q-1) = (1 0)

so we perform the A←(A-M) operation, according to the figure each time when we perform any operation in register A, we assume that its value is 00000000 for +M and 11111111 for −M. Performing A←(A-M) yields the first partial product

A = 11111111+00001001 = 11111001

Now, we have

count = 3(Q0 Q−1) = (1 1)

note here, when we have (Q0 Q−1) as (1 1) or (0 0), we'll just skip and put all 0s in the partial product by shifting it by 1 bit to the left (as we do in multiplication) as it's done in the book, which is the 2nd partial product

A = 00000000+00000000 = 00000000shifting it left by 1 bit, 00000000

Now, we have

count = 2(Q0 Q−1) = (0 1)

so we perform the (A←A+M) operation, which gives us the 3rd partial product

A = 00000000+00000111 = 00000111shifting it left by 2 bits, 00011100

Now, we have

count = 1(Q0 Q−1) = (0 0)

as mentioned above, we'll just skip and put all 0s as the 4th partial product

A = 00000000+00000000 = 00000000shifting it left by 3 bits, 00000000(this isn't illustrated in the figure 9.14(a))

after this operation count = 0 and then we'll sum up all the partial products as
   11111001 (1st partial product)
   00000000 (2nd partial product)
   00011100 (3rd partial product)
 + 00000000 (4th partial product)
-------------------
   00010101 (final product)

As we all know (00010101)2 = (21)10. That's what done in the figure 9.14(a), but shown in a different (or COMPACT) way as
   11111001
   0000000
 + 000111
-------------------
   00010101

Well, you can make it more compact like this:-
   11111001
 + 000111
-------------------
   00010101

But all of 'em will give you the binary representation of 21.


For each $i$, find minimal $j>i$ such that $A[j]>A[i]$ I have the following problem:

Given an array $A$, I need to construct an array $B$ such that $B[i]$ is the minimum $j>i$ such that $A[j]>A[i]$, or Null if no such $j$ exists.
For example, if $A = [23,45,13,10,33]$ then $B = [2,Null,5,5,Null]$.
The algorithm should run in time $\Theta(n)$.

its next greater element problem
its solvable using stack
u can learn it from here (in method 2)
for more practice of this useful method u can solve these problems:

Largest Rectangle
https://www.hackerrank.com/challenges/largest-rectangle/

And xor Or
https://www.hackerrank.com/challenges/and-xor-or

Poisonous Plants
https://www.hackerrank.com/challenges/poisonous-plants

196A - Codeforces
http://codeforces.com/problemset/problem/196/A

319B - Codeforces
http://codeforces.com/problemset/problem/319/B

Minimum Sum
http://agc005.contest.atcoder.jp/tasks/agc005_b

these are solvable using #next_greater_element


Constructing a data structure supporting prioritized key lookup so this is more or less a shot in the dark as I am feeling stuck. Maybe some of you have an idea which helps.

Here is the problem description (pseudo formal):

I want to have a structure $T = \{ \hat{x_1}, \hat{x_2}, ... \}$ with $\hat{x_i} = (p_i, k_i, v_{k_i})$.

$p_i \in \mathbb{N}$ can be interpreted as an associated priority. They can be considered unqiue.

$k_i \in \mathcal{K}$ a key index, $d := |\mathcal{K}|$ is not required to be negligibly small, though generally $d \lt\lt |T|$

$v_{k_i} \in \mathcal{V}^{(k_i)}$ a partial key over some universe associated with the given key index. As a little pace killer, this key may not be hashable. The only requirement is totally ordered.

Considering an array $y = [v_i], i \in \mathcal{K}$,
the structure should be capable of supporting the following operations efficiently:

$lookup(T, y) \rightarrow \underset{x_i \in T : y[k_i] = v_{k_i}}{arg max}( p_i )$, i.e. the node $\hat{x_j}$ with a partial key matching and the highest associated priority.

$succ(T, y) \rightarrow lookup(T \backslash \{\hat{x_j}\}, y)$, i.e. the successor (in terms of priority) of a node $\hat{x_j}$ matching $y$

Ultimately I would also like efficient insertion and deletion (by priority).

(For insertion: The selection of $k_i$ for each node is another point of research and can by chosen at the time of insertion. It is essentially possible that this key index is subject to change if it helps the overall structure. But it is also not required that all key indices in $\mathcal{K}$ are supported for each node, i.e. one might need to insert a node which is only queryable by a single $k_i$.)

The key indices are somewhat causing a headache for me. My research so far includes standard priority search trees and dynamic variations thereof.
I also found this very interesting, though very theoretical, paper which takes care of the increased dimensionality (kind of) caused by the d-dimensional keys.

I know that I can construct d-dimensional binary search trees with a query complexity of $O(d + n log(n))$. These should definitely yield a gain though I am not capable of mapping the priority problem to it (Ref).

But I guess the complexity can be reduced even further if we consider that fact, that each node is only storing partial keys anyway.

My approach so far is somewhat naive as it simply creates a hash map for each key index in $\mathcal{K}$ and queries each hash map upon lookup. It then aggregates all the results and sorts them by priority.
This works fine for hashable keys but a fallback structure has to be used whenever they are not (I am using binary search trees).

Edit:

To clarify:
I would like to find a solution which is sub $O(d log(n))$ for queries.

The successor problem can be solved in at least $O(d)$, even if using some kind of tree. See this resource for an overview.

One approach is to use $d$ binary search trees, one tree per element in $\mathcal{K}$.

The tree for $k \in \mathcal{K}$ stores all items $\hat{x_i} = (p_i, k_i, v_{k_i})$ such that $k_i=k$, keyed on the value $v_{k_i}$.

To insert an item, insert it into the appropriate tree.  This can be done in $O(\log n)$ time.

The lookup operation can be done by searching in each binary tree, and taking the best match.  When searching in the tree for $k \in \mathcal{K}$, you search for the key $y[k]$.  This takes $O(d \log n)$ time.

The successor operation can be implemented similarly to the lookup operation, and also takes $O(d \log n)$ time.

You can speed up the operations to take expected $O(1)$, $O(d)$, and $O(d)$ time (respectively) by replacing each binary search tree with a hash table.


Why sum of two binary numbers cannot be determined in $NC^0$ but in $AC^0$? Why sum of two binary numbers cannot be determined in $NC^0$ but it can be determined in $AC^0$?

In an $\mathsf{NC^0}$ circuit, every output bit depends on a bounded number of input bits. But the $k$th bit of the output (counting from the LSB) depends on the first $k$th bits of each input.

To see that $\mathsf{AC^0}$ circuits can compute addition, we need to produce such a circuit. Hopefully you have seen such circuits, and otherwise perhaps you can construct them on your own. Give it a shot.


Asymptotic Properties of Functions in Complexity Analysis When dealing with the analysis of time and space complexity of algorithms, is it safe to assume that any function which has tight bounds ( i.e. $f(n)=\Theta(g(n))$ is asymptotically positive and asymptotically monotonically increasing.  I mean that for all $n$ greater than or equal to some $n_0$ both those properties hold?

It is safe to assume that $f$ is everywhere positive, hence, asymptotically positive. You can't use negative time or space.

It is not safe to assume that $f$ is asymptotically monotonically increasing, since this excludes constant functions, i.e., those which are $\Theta(1)$.

It isn't even safe to assume that $f$ is asymptotically monotonically non-decreasing; this precludes functions that oscillate. A good question might be "do any useful algorithms have asymptotically oscillating time or space complexities," but certainly you could create an algorithm that did.

I suppose a more rigorous answer would ask what your definition of "asymptotically monotonically increasing" means. If it means that it's $\Theta(g(n))$ where $g(n)$ is monotonically increasing for positive $n$, then the answer would be yes, by definition.


Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems? To prove that some decision problem $A$ is NP-complete, my understanding is that it suffices to show that the problem is in NP (i.e. that one can verify or reject all statements in polynomial time), and to demonstrate that some known NP-complete problem $B$ can be reduced to $A$ (such that we can write $B \leq_p A$), by some kind of appropriate reduction in polynomial time.  We can then say that we can solve $B$ in polynomial time with an oracle for $A$.

One famous example of this would be the reduction of 3SAT to 3-coloring.

So sure, I understand that with an oracle for 3-coloring, one could solve arbitrary instances of 3SAT in polynomial time.  But why would I assume the converse holds, that I can solve arbitrary instances of 3-coloring provided an oracle for 3SAT?  The 3SAT $\leq_p$ 3-coloring reduction, of course, requires the use of special and restricted graphs where a 3-coloring exists iff a satisfying assignment for the 3SAT problem exists.

Doesn't this conflict with statements (at least I thought I heard in CS classes) saying that an oracle for 3SAT would prove P = NP?  Might it not be the case that such an algorithm would be worthless for solving families of 3-coloring problems?

Doesn't this imply some kind of hierarchy of NP-complete problems?

(Said a bit differently: If an oracle that allows one to solve a single NP-complete problem in polynomial time must necessarily be an oracle that allows one to solve all NP-complete problems in polynomial time, shouldn't we need to show $B \leq_p A$ AND $A \leq_p B$, where $B$ is some known NP-complete problem, to prove that some problem $A$ is NP-complete?)

But why would I assume the converse holds, that I can solve arbitrary instances of 3-coloring provided an oracle for 3SAT?

3-SAT is $NP$-complete, by the Cook-Levin theorem. This means that any problem in $NP$ (such as 3-coloring) can be solved in polynomial time given an oracle for 3-SAT.

  shouldn't we need to show $Q \leq_p P$ AND $P \leq_p Q$, where $Q$ is some known NP-complete problem, to prove that some problem $P$ is NP-complete?

Yes, but you essentially get the $P \leq_p Q$ for free because $P$ is in $NP$ and $Q$ is $NP$-complete.


Is there a term for the common semantics of global variables, static local variables, and fields? I'm working on a graph representation of software for a static analysis project, and I'm finding a distinction that I have no name for between different types of variables.

On one side of the division, we have local variables and parameters, which are not subject to modification by other threads during the execution of a method. For these variables, static single assignment form is valid.

On the other side of the division, we have global variables, fields, and C/C++ static local variables, which can be modified by other threads, meaning static single assignment form is not necessarily valid, as the variable may be modified by a separate thread during the execution of the method.

Is there any existing term for this division?

One standard term is "shared mutable state".

Let's unpack that.  "State" is any place to store data: e.g., a variable or object.  "Mutable" means that the data can be modified.  "Shared" means it is shared among multiple threads.  Thus, shared mutable state is state that is visible to multiple threads and can be modified by multiple threads.

Usually, immutable state is not a concern: even if it can be read by multiple threads, no one can write to it, so there is no potential for data races or concurrence problems.

Usually, non-shared state is not a concurrency concern: there's only a single thread that can read or write it, so we don't have to worry about concurrency -- merely single-threaded-correctness.

Note that this also helps clarify how we should think about a case that wasn't mentioned in your original question.  What about state that can only be written by a single thread, but can be viewed by multiple threads?  That's shared mutable state.  And that's exactly the right classification, because such state can cause concurrency problems: if you're not careful, it can cause data races and other issues, so it's only right that it be lumped together with other kinds of shared mutable state.

(For instance, in your question you write that "local variables... are not subject to modification by other threads during the execution of a method".  This is true, but it doesn't go far enough.  The relevant fact about local variables is that they can't be modified or read by other threads.  Also, this highlights that not all local variables qualify: for instance, if you take the address of the local variable and pass that pointer to another thread, the local variable now becomes shared mutable state and is a concurrency problem.)


Why does taking a gamma value > 1 make the image darker? If I've understood gamma correction correctly (and I probably haven't), a gamma transform to an image raises the value of the intensity level of the input pixel to the power of gamma, where gamma can be greater than one or less than one.

Pout = (some_constant) x Pin^(gamma)

In every example that I've seen, a gamma value < 1 makes the image lighter (raises intensity of lower intensity pixels) and a gamma value > 1 makes the image darker. This seems counter intuitive to me since a gamma value > 1 should increase the intensity levels of all the pixels making it lighter and more saturated.

Can someone explain this to me? Where am I going wrong?

Because pixel intensity in any professional task is measured between [0; 1].

The most representations are 8bit per pixel but there are for example 16bit representations.
So with [0;1] intensities there is always good representation device independent.

Another important thing is chaining operations (multiply, add pixels etc.), floating points are better because they store fractional values.
If you have RGB from 0-255 it is one way of representing it, very common, discrete but device dependent.
In such representation operations on pixels like gamma needs normalisation by division: divide by 255, apply operation, then cut to [0; 1] and then multiply by 255.
In floating point operation this is not needed.
Also look out for shifted gamma corrections, in colour space conversion for example.

Summing it up [0; 1]$^\gamma$ is going counter-intuitive.


How to optimize a function by maximizing 1 variable and minimizing another? Problem

I want to implement an optimization algorithm for my file transfer program.

The program buffers data in a local file before uploading to central server periodically and it compresses the files before transferring.

I would want the program to intelligently predict the time and size thresholds before transferring.

The objective function could be defined as following

f(u) = theta1*u + (theta2*u)/b + theta3

where

u is the size of data
b is the network bandwidth (bps)
f(u) is the time taken to transfer u bytes of data.
theta1*u refers to amount of time taken to compress u bytes of data
theta2*u*b refers to time taken to transfer compressed data.
theta3 is constant protocol overhead

I want to be able to optimize the transfer by minimizing time and maximizing uncompressed size.
If I were to simply minimize f(u) that would have been easy but then in this particular case , I would also want to maximize amount of data to be transferred.
The idea is to be able to come up with a machine learning algorithm which can change as per different network scenarios and fluctuating bandwidth , rather than user providing it at start of program.

Of course, I would implement it with some sane seed values and keep them within sane boundaries.

Solution space

Given the nature of this problem , which class of algorithms should I be looking into? Would gradient descent be the right way to approach this? is it possible to apply maximize and minimization on same function of 2 different variables? Am I over-thinking this ?

You can't.  The optimal solution is not well-defined.  In general there will be a range of tradeoffs between minimizing time and uncompressed size, and you haven't specified anything that would allow uniquely identifying which you want.

Your first step is that you need to specify a single objective function, where the goal is to find a solution that maximizes the objective function.  Then you can try applying standard methods from mathematical optimization, e.g., gradient descent, Newton's method, and so on.


Determining Length of a walk in Nondeterministic Finite Automata with Lambda Transitions I am learning about CS Theory and specifically Nondeterministic Finite Automata (NFA) right now. In my book I came across a section of text that discussed a way to determine the length of a walk stating specifically that :

  If a transition graph has a walk labeled $w$, then there is a walk w of length no more than $\Lambda + (1 + \Lambda)|w|$ where $\Lambda$ is the number of $\lambda$ transitions in the graph.

The book does not define $|w|$ which is causing part of my confusion. I'm assuming $|w|$ is the length of the label of the walk. So in this case it would be 1 when going from $q_1 \to q_0 \to q1$ because $a$ is the only labeled edge.
I am trying to understand this concept and how it works because when I have tested out this claim it has not held true.

Here is the test I did with this NFA

$q_1$ is the final state. So assuming you were trying to find the length of the walk $a$, the label would indicate that the length is 1 (e.g. $\delta^* (q_1, a)$) . However due to the lambdas you actually have $\lambda \lambda a$ to go from $q_1 \to q_0 \to q_1$.

This theorem doesn't hold with my math though because it is defined as Λ + (1 + Λ)|w| where Λ is the number of λ-edges in the graph.

Since there are two λ-edges (and it doesn't state whether it means λ-edges in the walk itself or in the graph in total...) this would then be 2 + (1 + 2)|w|. So thats 2 + 3|w|. This clearly is more than 3, which is the length of q1 -> q1 of λλa.

What am I missing here? Any help is greatly appreciated.

This comes from Peter Linz "An Introduction to Formal Languages and Automata" 5th edition.

Some more information about the argument for this claim:

  While λ-edges may be repeated, there is always a walk in which every repeated λ-edge is separated by an edge labeled with a nonempty symbol. Otherwise, the walk contains a cycle labeled λ, which can be replaced by a simple path without changing the label of the walk.

Also the book never names this as a theorem or lemma or anything of the sort so it has been very difficult to find online resources about this topic.

The length of the walk is the number of edges in the walk. Suppose $p$ is a walk labeled $w$. We can decompose $p$ into $p_1 e_1 p_2 e_2 \cdots p_{|w|} e_{|w|} p_{|w|+1}$, where each $p_i$ consists only of $\lambda$-transitions, and $e_i$ is a transition labeled $w_i$. There is always an equivalent walk in which no transition is taken twice in each $e_i$ (this is what is proved in the paragraph you quote), and so $|p_i| \leq \Lambda$. Therefore the entire walk has length at most $(1 + \Lambda) |w| + \Lambda$.


Shortest Path in a Graph with Interacting Edge Weights Suppose we have a graph $G = (V,E)$.

Every edge $e \in E$ has a unary cost $f(e) > 0$.

Also, for every two edges $e_1,e_2 \in E$ we have a binary reward function $g(e_1,e_2) \geq 0$.

Given two vertices $s$ and $t$, is it possible to find the path that minimizes the following objective function efficiently?

$
\sum_{e \in \text{Path}} f(e)
- \sum_{e_1 \in \text{Path}} \sum_{e_2 \in \text{Path}} g(e_1,e_2)
$

Update:

According to @xavierm02's answer this problem seems to be NP-hard. But is there any heuristic that can at least partially deal with this? If it helps, this is the context for which I want to use this problem.

This shortest path simply represents a sequence of curves for a piecewise curve fitting as in the paper: http://www.mit.edu/~ibaran/curves/ .

The final goal is to fit a sequence of curves to a bunch of points. As we cannot fit just one curve, we also have to decide where the transitions occur. In this approach, we basically fit every possible curve. Then, we construct a graph, where each curve is associated with an edge, and the points to be fitted are the vertices (not exactly the same as the paper). The weight of each edge is basically its error in the least square fit. We then find the shortest path from the first point, to the last, which in turn tells us the best sequence of curves.

What I am trying to do is to use this reward function to encourage certain curve pairs to be inside the final selected sequence of curves. For example, the ones that are symmetric.

Further updates:

$g$ has very few non-zero values, and we can safely assume $g(e_1,e_2)<f(e_1)$ and $g(e_1,e_2)<f(e_2)$. The graph has cycles, and we might have $s=t$.

It's NP-hard.

We reduce 3SAT to your problem (where $f$ is constant). Let $c_1,\dots ,c_m$ be an instance of 3SAT. Let $v_1,\dots,v_n$ be the variable in the clauses. For each clause $c_i$, call $l_{i,j}$ the $j^\text{th}$ literal of $c_i$. Now, build this graph:

(Note that we allow several edges between the two same nodes, but if you don't want to, you can just add dummy nodes)

Now, if we look at paths from $0$ to $n+m$ in this graph, clearly, they will pick a value per variable (true if it picks $v_i$ and false if it picks $\lnot v_i$), and a literal per clause. Set $f:=e\mapsto 1$ to be constant. Now set $g((l,c),l)=1$ and $g(e,e')=0$ in all other cases, i.e. reward taking a literal in a clause that's been made true by the valuation defined by the first $n$ edges. Note that the cost of a path from $0$ to $n+m$ is $\le n$ (or equivalently $=n$) if and only if the initial formula is satisfiable (because the cost due to $f$ is $n+m$ and the reward due to $g$ is the number of satisfied clauses). So the problem "Is there a path of cost $\le n$" is NP-hard.


Prove correctness of this (context-free) grammar I created a context free grammar for the language which has words where twice as many a than b occur.

So as example, the language would accept the words baaaab and bbbaaaaaa, aab, etc.

The context free grammar is

G = ({X} {a,b}, P, X)
P: X -> XaXaXbX, XaXbXaX, XbXaXaX, epsilon (where epsilon is the empty word)

Now how can you justify the correctness of this grammar? So I'm not asking for a strict proof, just rather a way to reason the correctness of this grammar.

The smallest possible strings are aab, aba, baa.

And somewhere, in between one of these characters, you can insert any of these three possibilities or just the empty word epsilon.

You will always end up with twice as many a than b because all our combinations satisfy this condition and we are only using these conditions. So in the end the condition will be the same and be satisfied.

Would you count this as a "reasoning of correctness"? If I read what I have written once again, it sounds a bit cheap :p

Now how can you justify the correctness of this grammar?

In order to prove that some grammar $G$ generates a language $L$, i.e. $L= L(G)$, you need to prove two things:

for any string $w \in L$, $G$ yields/generates $w$, i.e., $S \Rightarrow^* w  $, and
for any string $w$ (consisiting of only terminal symbols), if $G$ yields/generates $w$, then $w \in L$

In your particular example, you first need to prove that if $w$ has twice as many $a$s than $b$s then your grammar $G$ yields $w$, and if $G$ yields some string $w$ then $w$ has twice as many $a$s than $b$s. Induction on the length of $w$ or the number of steps of application of derivation rule might be helpful.

This is our reference question which may be helpful to prove that a language is context free.


Convert the given NFA to DFA I am trying to find an DFA for the regular language given by the expression $L\left( aa^{\ast }\left( a+b\right) \right)$.
First simplifying $L\left( aa^{\ast }\left( a+b\right) \right)$ we get
$L\left( aa^{\ast }\left( a+b\right) \right)$ $= L\left( a\right) L\left( a^{\ast }\right) L\left( a+b\right) $
Then I constructed an NFA for it , which is given below :

But I am not able to simplify the above NFA to a DFA as the state $q_1$ has two $\lambda$ transitions and I am not understanding how to deal with them .

See this page.
Essentially, create a new DFA $D$ in which the set of states $Q$ is the powerset of the set of states of your NFA $N$.
For $q \in Q$ and $a \in \Sigma$, add transition $\delta(q,a) = q'$ to $D$, if and only if, the set of states of $N$ that are reachable (in $N$) from at least one state in $q$ by reading character $a$ is exactly $q'$.
Mark a state of $q \in Q$ as a final state in $D$ if and only if $q$ contains a final state of $N$.
If $q_0$ is the initial state of $N$, then the initial state of $D$ is the set of states if $N$ that are reachable by $q_0$ using only $\varepsilon$-transitions.


How can I make automaton that has given language? I am trying to solve above question, below is the automaton I came up with:

Is there any ways to define automaton without having marked states?

You want to make an automaton that accepts the language
$L_1 = \{ s \in \{a, b\} \mid \text{each $a$ in $s$ is immediately preceded and followed by }b \}$.

A few examples of words that should be accepted are:

$\lambda$ , which is the empty word. There is no $a$ in the empty word so this word should be accepted.
$b^*$, which is any word only containing $b$'s.
Other examples: $bab$, $bbbbbab$, $babababab$.

So let's start constructing. Since the empty word is accepted, the initial state $q_0$ should be an accepting state. A word starting with $a$ can't be accepted, therefore we forward such a word to $q_3$ and let it be stuck there. $q_3$ is not an accepting state.

Now consider a word starting with $b$. The word $b$ should be accepted, so $q_2$ is an accepting state. $b^*$ should be accepted, therefore we define the transition function $\delta(q_2, b) = q_2$. (Any $b$ in $q_2$ goes to $q_2$.)

Now the transition from $q_2$ to $q_4$ is triggered by an $a$. $q_4$ is not an accepting state. If there is another $a$, we know that the input should not be accepted so we define the transition $\delta(q_4, a) = q_3$. Once in $q_3$ it will loop there, so the word can't be accepted.

The transitions between $q_2$ and $q_4$ make sure that any word ending with b is accepted, provided that a sequence of multiple $a$s never occurs. If it does it will go to state $q_3$ and it will be stuck there.


Utility of D latch/flip-flop and how it differs from an SR latch/flip-flop I understand that in a D latch, whenever the clock signal is high, Q matches D, and while the clock signal is low, it holds the previous state of D. For a D flip-flop, Q will hold whatever value D is at the exact moment C goes high, and will hold that same state until C goes high again. I am able to draw the clock diagram and identify these circuits. But I am not understanding the purpose of these components in a high level context.

What exactly does the D latch and D flip-flop do? (Differences and similarity)
From my understanding, it is to be able to "store" a bit value, but if that's the case, why not use an SR latch?

Edit: I have seen the following post. However, my question is a little more specific. I am asking specifically about a D latch/flip-flop. I also want to be able to differentiate how this is different from a SR latch, since it seems that their descriptions seem to do the same thing.

One big difference is that while the SR flipflop has a "not-allowed" state (i.e., inputs S=1, R=1), the D flipflop has no such condition.

Another difference, is that the D flipflop just mirrors the input into the output, while SR has two inputs: one for setting the ouput to 1, and one for resetting the output into a 0.


Is every acyclic graph 2-colorable? Every acyclic graph can be transformed structurally to a tree. Therefore, every node on odd numbered levels can be colored with color $X$ and every node on even numbered levels can be colored with color $Y$. Is the reasoning valid?

An acyclic graph, usually known as a forest, is a collection of disjoint trees. It is only a tree if it is connected. Since trees are 2-colorable (for the same reason you mention), it follows that forests are also 2-colorable.

It is also possible to reduce the general case to the connected case: given a forest, you can join the different connected components to form a tree. The resulting tree is 2-colorable, and the same 2-coloring is also valid for the original forest.


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

Thanks.

The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys is an excellent handbook on approximation algorithms. It has an entire chapter devoted to the topic of SDPs. As of now you can download the older version directly from their website; however the printed text is pretty affordable.


Why is $ZPP \geq BPP$ not true? This seems like a silly question, but I couldn't find a conclusive answer for it.

As far as I know, ZPP contains algorithms which run in polynomial time and either return a known-correct answer or abort (this definition is equal to the one where they either return a correct answer or run in exponential time). It is also possible to get the failure probability of a ZPP algorithm  arbitrarily low (but $>0$) by rerunning it often enough without using exponential time.

BPP contains algorithms which will always return an answer in polynomial time, but this answer may be wrong with at max a $\frac{1}{3}$ chance.

Therefore, given a solver for ZPP problems, I can create a function which either solves my problem or abort in $\frac{1}{3}$ of the cases, while running in polynomial time$^1$.

Given this function, I can solve any problem contained in BPP by running the function created above on it and return a random response if it aborts. Since this will be in less than $\frac{1}{3}$ of the cases, the probability for a wrong answer will be less than  $\frac{1}{3}$ and it will always run in polynomial time.

This would imply that BPP is contained in ZPP, but it seems that it is actually the other way around. So where am I wrong?

$^1$ This might be my error, but it's described like this in our lecturer slides (which are not public). I couldn't find a direct citation for it, but Complexity Zoo states for RP: "implicitly: the class VPP that is defined is equivalent to RP by running the recognizer as many times as necessary to reach probability 1/2?", so I assume this can be applied to ZPP as well and my understanding is correct.
EDIT: Also, in case this doesn't hold true, at least ZPP($\frac{1}{3}$) should be equal to BPP, which I couldn't find anywhere either.

You explain how to convert a ZPP machine to a BPP machine. This means that if a problem is in ZPP, then it is also in BPP. In other words, ZPP is contained in BPP.


An algorithm for fitting a rectangle inside a polygon I have a kind of cutting problem. There is an irregular polygon that doesn't have any holes and a list of standard sized of rectangular tiles and their values.

I want an efficient algorithm to find the single best valued tile that fit in this polygon; or an algorithm that just says if a single tile can fit inside the polygon. And it should run in deterministic time for irregular polygons with less than 100 vertices.

Please consider that you can rotate the polygon and tiles. Answers/hints for both convex and non-convex polygons are appreciated.

Let $P=(p_1,\dots,p_n)$ be the polygon and $\overline{P}$ the set of points it contains.

Let $R=(a,b,c,d)$ be the rectangle of width $w$ and length $l$ with $l\ge w$ (and we assume $d(a,b)=w$) and $\overline{R}$ the set of points it contains.

You want $\overline{R}\subset \overline{P}$.

Suppose $\overline{R} \subset \overline{P}$.

Let $q=a+\cfrac{1}{2}\vec{ab}$ and $r=c+\cfrac{1}{2}\vec{cd}$.

Since $q\in [ab]\subset \overline{R}$ and $r\in [cd]\subset \overline{R}$, $[qr]\subset \overline{P}$.

Since $q\not=r$, we can find $s$ and $t$ on the border of $P$ so that $(qr)=(st)$.

Now suppose you are given a convex $P$

Here's the algorithm:

$\forall i \in [1,n]$

$\forall j \in [i+1,n]$

If $\max \{d(x,y),x\in[p_ip_{i+1}],y\in[p_jp_{j+1}]\}\ge l$

$s = p_i + k_1 \vec{p_ip_{i+1}}$
$t = p_k + k_2 \vec{p_jp_{j+1}}$
$q = s + k_3 \vec{st}$
$r = q + \cfrac{l}{\|\vec{st}\|}\vec{st}$
$\vec{v}:=$ a vector so that $\vec{sr}\perp \vec{v}$ and $\|\vec{v}\|=\cfrac{w}{2}$
$a := s - v, b:= s + v, c := r+v,d:= r-v$
$S:=solve(\{"k_1\in [0,1]", "k_2 \in [0,1]", "k_3 \in [0,1]", "a,b,c,d\in P"\}$
If $S\not= \emptyset$, return true

return false

The way this algorithm works is it chooses an orientation and an ax for the rectangle by choosing two arbitrary points $s$ and $t$ somewhere on two arbitrary segments of $P$. Then it takes an arbitrary $q$ in $[st]$ and expresses $a,b,c,d$ in terms of the constants $k_i$ determining $s,t$ and $q$. Then for a point, you know how to determine if it is in a convex polygon so you just need to solve those linear inequalities (in $k_1,k_2,k_3$) for all $4$ points. And if you have solutions, $R$ fits in $P$. Otherwise, you just try another one. And if none worked, since we know that if $R$ fits in $P$, then at least one must work, we know $R$ doesn't fit in $P$.

NB: $\max \{d(x,y),x\in[p_ip_{i+1}],y\in[p_jp_{j+1}]\}=\max\{d(p_i,p_{i+1}),d(p_j,p_{j+1}),d(p_i,p_j),d(p_{i+1},p_{j+1})\}$

Then for the non-convex case, you loose the fact that: $a,b,c,d\in \overline{P}\Rightarrow \overline{R}\subset \overline{P}$. So I'm not sure how to do it.

If I had to try, I'd break $P$ into several convex polygons and try to apply a similar algorithm except that I'd try every recombination of $A,B,C,D$ with $a\in A,\dots,d\in D$ with $A,B,C,D$ different convex polygons forming $P$ and then check that the segments of $R$ don't cross segments of $P$...


$2$-sorted array. How to sort it in minimal number of comparisons ? It is given array $2$-sorted array $a[1..n]$.  $2$-sorted denotes that $a[1]\le a[3]\le...\le$ and $a[2]\le a[4]\le ..\le$

Obviously we may split array into two sorted arrays and then merge two arrays - it requires $n-2$ comparisons.  However I think about lower bound. I believe that $n-2$ is lower bound number of comparisons, but I can't see a way to prove it.  Can you give me a clue ?

Hint:Show that the algorithm must compare the following pairs:
$$ (a[1],a[2]), (a[2],a[3]), (a[3],a[4]), \ldots, (a[n-1],a[n]). $$

For each comparison $(a[i],a[i+1])$, assume that you haven't compares $a[i]$ to $a[i+1]$ but you have done all other comparisons. Show that you still don't know the correct sorted order of the array.


Globally-optimized nearest neighbors lookup I have a set $\mathcal{A}$ of $\mathcal{m}$ vectors in $\mathbb{R}^a$. I also have a different set $\mathcal{B}$ of $\mathcal{n}$ vectors  in $\mathbb{R}^a$.  These two sets are disjoint: $\mathcal{A}\cap\mathcal{B} = \varnothing$.

My goal is to find a set $\mathcal{C}$ such that $\mathcal{C} \subset \mathcal{A}$ and $\vert\mathcal{C}\vert = \vert\mathcal{B}\vert$, that minimizes the sum
$$
\sum\limits_{j}\Delta(\mathcal{C}_{j}, \mathcal{B}_{j})
$$
where $\Delta$ is some distance metric.  All elements of $\mathcal{C}$ must be unique, and there are no restrictions on the ordering of sets $\mathcal{B}$ or $\mathcal{C}$ in the calculation of the above formula.  The crucial challenge here is that we can't match two different points of $\mathcal{B}$ to the same point of $\mathcal{A}$, so you can't just assign each point of $\mathcal{B}$ to its nearest neighbor in $\mathcal{A}$.

Is this equivalent to an already-studied problem? If so, which problem?
Assuming the answer to 1 is yes, are there better approaches than the greedy one?

Answer to 2 is optional, I can do the research myself, just having difficulty nailing down an equivalent problem.

Here's one approach -- not necessarily the fastest.  This can be viewed as an instance of the assignment problem, or equivalently, finding a minimum weight perfect matching of a bipartite graph.  Imagine a bipartite graph with $\mathcal{A}$ being the set of vertices on the left, $\mathcal{B}$ being the set of vertices on the right, and an edge between every pair of vertices  whose weight is equal to the distance between those points.  Now you are looking for a perfect matching of minimum weight.  Once the graph is built, there are standard algorithms for this, such as the Hungarian algorithm or linear programming.

The first step in such an approach is to compute all-pairs distances, i.e., the distance between every point in $\mathcal{A}$ and every point in $\mathcal{B}$.  This takes $O(nma)$ time.  Based on your original question, it appears that $n \approx 20$, $m \approx 50,000$, and $a \approx 800$, so that part should be very fast.

Unfortunately, the Hungarian algorithm might be too slow.  The running time in this setting will be $O((n+m)^3)$, which might be too slow for your needs.  I think a tighter analysis shows that its running time is actually $O(n^3m)$, which might be fast enough for your needs, but I'm not certain about that.

If the Hungarian algorithm is too slow, here is a heuristic that you could try.  In each stage, we'll have a non-optimal solution and iteratively try to improve it.  (You can start with the greedy solution, to get the process started.)  Suppose our current solution assigns $f(b_j)$ to the point $b_j$.  Let $t$ be a threshold.  Filter the graph to include only edges $(a_i,b_j)$ where $\Delta(a_i,b_j) \le \Delta(f(b_j),b_j) + t$, and delete all isolated left vertices.  Now find a minimum weight perfect matching in that graph.  That will be a new solution that is at least as good as the previous solution.  In each stage, increase $t$ according to some schedule.  If you keep $t$ small, this won't necessarily give you the optimal solution, but it will make the Hungarian algorithm more efficient because it works with a smaller graph.

Theoretically, you can find a value for $t$ that enables you to prove that this will find the optimal solution (namely, a lower bound for the sum can be obtained by matching each element $b_j$ to its nearest neighbor in $\mathcal{A}$, ignoring the constraint that the elements of $\mathcal{C}$ be unique, and summing those distances; now if you let $t$ be at least the difference between the cost of the current solution and that lower bound, and apply this scheme, if it converges -- yields the same solution you started with -- then you know you've found the optimal solution).  However I don't know whether that will be useful in practice.

Anyway, this is one approach.  It might not be the best or fastest, because it doesn't take into account the geometrical structure.  But it's something you could try, to see if it meets your needs.


Closed form solution of $T(n) = 5T(n-1) + n^2$ How to find the closed form solution of this equation? Is there a repeatable pattern for solving this equation?

$$T(n) = \begin{cases}
1 & n = 1\\
5T(n-1) + n^2 & \text{otherwise}
\end{cases}$$

How to find the closed form solution of this equation?

This is linear nonhomogeneous recurrence relation of the form $a_n = a_n^{h}+a_n^{p}$ where former expression in the right hand side is homogeneous solution while later one particular. Now, $a_n^p$ becomes $p_2n^2+p_1n+p_0$ whereas $a_n^h$ becomes $\alpha5^n$. Now solve them.

Another straightforward approach is to recursively solve the equation as follows
$$\begin{align*}
T(n) &= 5\cdot T(n-1)+n^2 \\
     &= 5[5\cdot T(n-2)+(n-1)^2]+n^2 \\
     &= 5^2T(n-2)+5(n-1)^2 + n^2 \\
     &= 5^3T(n-3)+5^2(n-2)^2 + 5(n-1)^2 + n^2 \\
     & \vdots\\
     &= \sum_{k=0}^{n-1}5^{n-k}\cdot k^2
\end{align*}$$

  Is there a repeatable pattern for solving this equation?

The very word recurrence implies pattern.


Is there constraint on reducibility while defining $\Sigma_i^p$? Sanjeev Arora and Boaz Barak define $\Sigma_i^p$ to be the set of languages such that if $L\in \Sigma_i^p$ then for every $x \in L \Longleftrightarrow \exists u_1 \forall u_2\ldots Qu_i M(x,u_1,u_2,\ldots,u_i) = 1  $ where $Q_i$ is $\exists$ or $\forall$ depending on whether $i$ is odd or even and $M$ is a Turing machine that runs in polynomial time. But there is no mention whether the reduction of membership of $x$ to the truth value of the statement $\exists u_1 \forall u_2\ldots Qu_i M(x,u_1,u_2,\ldots,u_i) = 1 $ takes place in polynomial amount of time. Am I misunderstanding something ?

In this definition, $M$ is constrained only to be a polytime relation, that is, you can compute $M$ in polynomial time. Note that there is no reduction here. The concept of reduction only comes up when you try to deduce that one problem is in a certain level of the hierarchy (or hard for a certain level of the hierarchy) given that another one is in some level of the hierarchy (hard for a certain level of the hierarchy).

For example, if $A \in \Sigma_i^P$ and $B$ polytime many-one reduces to $A$, then $B \in \Sigma_i^P$. If $A$ is $\Sigma_i^P$-hard and $A$ polytime many-one reduces to $B$ then $B$ is $\Sigma_i^P$-hard. If we consider reduction that are not polytime but are still in the polynomial hierarchy, we still get meaningful results that I encourage you to work out.


Leftist Heap doesn't support DecreaseKey operation? I'm studying data structure. When I read the chapter of heap, something really confused me. DecreaseKey's time complexity of the binary heap is O(lgn). However, I found somewhere on internet claimed that Leftist Heap doesn't support DecreaseKey operation. But I wonder why? Can't we simply treat leftist heap as binary heap to perform DecreaseKey?

Indeed, the right solution of DecreaseKey for leftist trees seems to be hidden on the internet. (My book by Weiss has a solution, but in the chapter on amortized analysis, and I do not quickly understand the argumentation.)

First, we cannot treat DecreaseKey as in binary heaps. There one repeatedly swaps the node with its parent until a parent is found which is actually smaller than the new value. This operation works in leftist trees, but may take linear time. In leftist trees there is no bound on the length of paths to the left, and indeed such a tree can be just one long linear leftmost tree.

The solution is to cut the node $q$ that is decreased (with its subtree), to change the value of $q$ to the new value, and merge it with the remainder $T$ of the original tree. Before we can do that we should bring $T$ back into leftist form, and restore the null-path-length values that are changed by cutting the subtree. As we cut $q$ from the tree, only the nodes from the parent $p$ upwards to the root have to be checked. (Unfortunately this may be a linear number of nodes, as we have seen.)

The solution is that the new null-path-length values we asign upwards in the tree are always one larger than the value at the previous level. This process stops when we are in a left child which has new value $\ell$ and its right sibling has value $r$ with $\ell \ge r$. Then the parent already had value $r+1 = \min\{\ell,r\}+1$ and we are done.

We know (from the basic property that makes leftist trees efficient) that a null-path-length value of $\ell$ means that there are $2^\ell-1$ nodes in that subtree, making the operation logarithmic.

The fact that the values upwards in the new tree are always one larger is essential here, that was not (necessarily) true along the path in the original tree.


Predict language from given expression $(b^* (aaa)^* b^*)^*$ I want to predict language from the given regular expression.

Regular Expression: $$(b^* (aaa)^* b^*)^*$$

As per my assumption language may be like:

Let the string contain alphabet $\{a,b\}$ where every string contain number of $'a'$ divided/multiply by $3$.

Let me know whether my assumption is correct or not.

Thanks

A simple counter example can be found for your answer. Take the string $$ababa$$ Here, the alphabet is $\{a,b\}$ and the number of $a$s is a multiple of $3$, yet it doesn't fit into the regular expression.

In the regular expression, $b^*(aaa)^*b^*$ denotes strings that contain an arbitrary (possibly zero length) sequence of $b$s, a sequence of $a$s that is a multiple of $3$ (possibly zero again), followed by an arbitrary length sequence of $b$s.

So, $(b^*(aaa)^*b^*)^*$ is such a sequence repeated over any number of times, including the empty string.

You could call the language as
$$L=\{x|x\text{ contains sequences of consecutive }\\a\text{s and }b\text{s, where the length of each sequence of }a\text{s is a multiple of }3\}$$

over the alphabet $\Sigma=\{a,b\}$.

In general, a language is just some subset of the set of all strings over a given alphabet. Given a language, there need not be any straightforward way of describing it in English. A regular expression, given the alphabet, completely specifies and describes the language.


Reductions among two problems related to walks of length $k$ Consider the following two problems:
A. Given a directed graph and a parameter $k$, determine if it contains a path (not necessarily simple) of length $k$.
B. Given a directed graph, two vertices $s,t$ and a parameter $k$, determine if the graph contains a path from $s$ to $t$ (not necessarily simple) of length $k$.
How can I reduce problem B to problem A?
I know that I can make a DFS tree at height $k$ with repeating vertices, however it solves the problem directly rather than by reduction.

Since $k$ is a constant you can solve $B$ in polynomial-time by exploring all $O(n^{k-1})$ paths of length $k$ starting from $s$ and ending in $t$, as you point out.
At this point the reduction is trivial:
If the answer to an instance $\langle G, s, t\rangle$ of $B$ is "yes" then the corresponding instance of $A$ is $G$.
If the answer to the instance  $\langle G, s, t \rangle$  is "no", then the instance of $A$ is the empty graph.


Given $k$ sorted lists, $O(n \log k)$ complexity, Mergesort rather than Heapsort I was convinced that my idea for a solution to sort $k$ sorted lists into one list would work with a 'variation' on MergeSort. I was told this would not work and had to use Heapsort, but didn't get any explanation or intuition behind it. (I believe the assumption is that each of the $k$ lists had size $\frac{n}{k}$)

Essentially, my intuition behind using Mergesort was that we have $n$ total elements, but all the steps below height $\log k$ in our recursion tree had already been solved. So at height $\log k$ each list is of size $\frac{n}{k}$, so we perform $\frac{n}{k}$ comparisons and $2\frac{n}{k}$ inserts (to form a new list from the two $\frac{n}{k}$ lists) $k$ times in total, which seems to be on the scale of $O(n)$.

We are now one step up on the recursion tree with $\frac{k}{2}$ lists and we will eventually perform $O(n)$ operations $\log k$ times.

Can anyone provide insight as to why this intuition is wrong? Or if right, how I should go about formally proving it?

I would structure a formal proof of the runtime of your strategy as follows (This is, in structure, very similar to what you already wrote, but does not refer to omitted steps of an imaginary run of Mergesort.):

Arrange the $k$ lists as the leaves of an (almost) complete binary tree. Each internal node of the tree represents the merging of the two lists in its children. Clearly this tree has a height of $\lceil\log k\rceil$.

In this structure, the merges on each level of the tree combined will process each element exactly once.[1] Thus, they take a combined time in $\cal O(n)$. Adding up over all levels of the tree gives a runtime in $\cal O(n\log k)$.

Note that this argument does not require the lists to be of similar size.

Depending on the audience you may be required to elaborate some more on the $\cal O(n)$ bound. This can be done similar to the reasoning in the question:

Merging two lists with size $n_1$ and $n_2$ takes $n_1+n_2$ inserts and (in the worst case) $n_1+n_2-1$ comparisons. Thus, if we perform $i$ merges on a combined total of $n$ elements, they take $n$ inserts and (in the worst case) $n-i$ comparisons.

[1] If $k$ is not a power of $2$, the lowest level processes only a subset of the elements. Obviously the bound still holds for this case.


Reference request: proof that if $L \in DCFL$, then $L \Sigma^* \in DCFL$ So, it's fairly easy to prove that if $L \in DCFL$, then $L \Sigma^* \in DCFL$. Basically, you take the DPDA accepting $L$. You remove all transitions on final states, and then for each $a \in \Sigma$ and each final state $q$, you add a transition looping from $q$ to $q$ on $a$.

I'm using this in a paper, and I'd love to not have to actually prove this construction is valid. It's easy, but it's about a half-page long. Since DPDAs have been studied almost exhaustively, I was wondering, does anybody know of a paper that proves this property?

One of the early works on DCFL is Seymour Ginsburg, Sheila Greibach: Deterministic context free languages, Information and Control, Volume 9, Issue 6, December 1966, Pages 620–648, doi:10.1016/S0019-9958(66)80019-0

The paper has various closure properties, for instance closure under complement (mind that my old Hopcroft and Ullman book states ".. was observed independently by various people") and closure under quotient with regular languages.

Closure of DCFL under concatenation with regular languages is the result you need, which is Theorem 3.3 from the paper.


Is multiple equation 0/1 linear integer programming with bounded integer weights NP-hard? Suppose we forget about optimizing and just want to find a feasible solution to a set of equations:

$$\sum_i w_{ij} x_i = W_j.$$

Here we are given $w_{ij}$ and $W_j$, and want to solve for $x_i$.  Also $x_i$ are restricted to be 0/1 and we're promised that $w_{ij}$ and $W_j$ will be non-negative integer constants and we will have $w_{ij} \leq M$ for some universal constant $M$.  The number of variables and equations can be arbitrary.

Is this an NP-complete problem? If we have just one or a universal bounded number of equations then the problem can be solved in polynomial time. Certainly if we can find a solution then we can verify it in polynomial time, so the problem is in NP. I was trying to find a reduction from something like 3-SAT in the general case but to no avail.

This problem is NP-complete, by reduction from 1-in-3 positive 3SAT.

1-in-3 positive 3SAT is a variant of 3SAT, where we require that exactly each clause consists of 3 positive literals (no negation), and to satisfy the formula, exactly one literal in each clause must be true (no more, no less).  Thus, each 1-in-3 positive 3SAT instance is a formula

$$\varphi(x_1,\dots,x_n) = \bigwedge_i (x_{c_{i,1}} \sqcup x_{c_{i,2}} \sqcup x_{c_{i,3}}),$$

where $x \sqcup y \sqcup z$ is true iff exactly one of $x,y,z$ is true.

You can immediately convert this to an instance of your problem.  In particular, the $i$th clause corresponds to an equation

$$x_{c_{i,1}} + x_{c_{i,2}} + x_{c_{i,3}} = 1.$$

For instance, the clause $(x_3 \sqcup x_5 \sqcup x_6)$ corresponds to the equation $x_3 + x_5 + x_6 = 1$.
We get one equation per clause.  The equations are simultaneously satisfiable iff the formula $\varphi$ is satisfiable.  This completes the reduction.


Computability of Stack Cleanliness Brain-Flak is a minimalistic, stack-based, Turing complete, esoteric programming language.

A big concern among Brain-Flak enthusiasts is a concept informally called "stack cleanliness".

The basic idea for stack cleanliness is that only certain values on the stack will be edited and all other values will remain unchanged

More formally:

Given an input arity (a tuple of positions on the active and inactive stack before the program runs), and an output arity (another tuple of the same sort after the program runs) and a function that maps between the two, a program is is considered stack clean iff it performs the function, ends on the stack it started, and the values on the stack that are not in the input remain the same regardless of the conditions of the stack.

The question is: Given a program that is known to halt for all input, a function and the two required arity tuples, is stack cleanliness computable?

I don't know the language in detail, but my guess is: no, stack cleanliness is not computable.

For every natural $n$, consider a Brain-Flak program $P_n$ which does the following:

take a natural $k$ as input;
without modifying the stack below, simulate Turing Machine number $n$ on empty input, for at most $k$ steps;
if the machine does not halt within $k$ steps, revert the stack to the original state, and return $0$;
otherwise, if it does halt, modify the stack below and return $0$.

$P_n(k)$ is guaranteed to halt for any inputs $n,k$.

$P_n$ will be stack-clean (on all inputs $k$, by definition) if and only if the TM number $n$ never terminates on empty input.

The latter is known to be undecidable (it's not even semi-decidable).

Hence stack cleanliness over input arity 1, output arity 1, and constant zero function is already undecidable.


n-Cube as a Cayley Graph I'm taking a class on graph theory that uses "Graph Theory (Graduate Texts in Mathematics)" by Bondy and Murty. One of the questions is about Cayley graphs and the n-cube, and I don't understand how to interpret it. It runs as follows:

  Let $\Gamma$ be a group and $S$ be a subset of $\Gamma$ not including the
  identity element. Suppose that the inverse of every element in $S$ also
  belongs to $S$. The Cayley graph of $\Gamma$ with respect to $S$ is the graph
  $CG(\Gamma, S)$ with vertex set $\Gamma$ in which two vertices $x$ and $y$ are
  adjacent iff $xy^{-1}\in S$.

Okay. I follow so far.

  Recall that the n-cube is the graph whose vertex set is the set of all
  n-tuples of 0s and 1s, where two n-tuples are adjacent if they differ
  in precisely one coordinate.

Makes sense.

  Show that the n-cube is a Cayley graph.

What does it mean to talk about "$xy$" when $x$ and $y$ are n-tuples? What is the inverse of an n-tuple?

Someone I asked about the problem suggested that I treat $\Gamma$ here as the additive group $({\mathbb Z}/2{\mathbb Z})^n$, and so take $xy^{-1}$ to mean elementwise subtraction of $y$ from $x$, mod 2. But then it seems like $(0, 0, ..., 0)\in\Gamma$ and, since it's the identity element, every vertex will have an edge connecting to it, and that isn't what the n-cube looks like. Googling, I also see that there is an interpretation of tuples as nested sets, but then I don't see how the product of two nested sets would ever be in S, since it will have a different cardinality from either of the original tuples. Interpreting the tuples as vectors can't work either since then $xy^{-1}$ will have different dimensions than either of the original tuples.

What is this question asking?

The question is asking you to find a suitable group $\Gamma$ and a subset $S$, so that $CG(\Gamma,S)$ is the n-cube.

Since by definition of $CG$, the nodes are the elements of $\Gamma$, you don't have a choice here, leaving the group operation and $S$.

$xy$ and the inverse of $y$ are then understood with respect to the group operation you choose.

Also be aware that the identity element being in $\Gamma$ does not imply that all other vertices are connected with it, since the edges are determined by $S$, not $\Gamma$.


Sum of two elements in set evenly divisible by k I have gone through this particular problem in hackerrank.

  You are given an array of $n$ integers, $a_0, a_1, a_2 , \ldots, a_n$, and a positive integer $k$. Find and print the number of pairs $(i, j)$ such that $i < j$ and $a_i + a_j$ is evenly divisible by $k$.

I wanted to make this work in $O(n)$ time. After lots of searching I found a solution online.

a = [1, 3, 2, 6, 1, 2]
k = 3
m = [0]* k
count = 0
for i in a:
    rem = i % k
    com = (k - rem) % k
    count += m[rem]
    m[com] += 1
    print(rem, com, count, m)
print(count)

This particular snippet works in $O(n)$ time. But I am having a hard time understanding whats going on mathematically, especially with rem and com variables.

Can anyone please explain me the aspect(mathematical) behind it.

This solution actually works in time $O(n+k)$. The idea is to maintain an array $m_0,\ldots,m_{k-1}$, where $m_r$ is the number inputs seen so far which leave a remainder of $r$ after division by $k$. When we see a new input which leaves a remainder of $r$ after division by $k$, we count $m_{k-r}$ new pairs (where $m_k = m_0$), and then update the array $m$.

A simpler solution is to first compute a histogram $m_0,\ldots,m_{k-1}$, where $m_r$ is the number of inputs in total which leave a remainder of $r$ after division by $k$. For each pair $s+t = k$, we count $m_sm_t/2$ pairs, and for $s=t=0$, we count $m_0(m_0-1)/2$ pairs (exercise), for a total of
$$ \frac{m_0(m_0-1)}{2} + \sum_{s=1}^{\lfloor k/2 \rfloor} \frac{m_sm_t}{2}. $$


What property of cons allows elimination of tail recursion modulo cons? I'm familiar with the idea of basic tail recursion elimination, where functions that return the direct result of a call to themselves can be rewritten as iterative loops.

foo(...):
    # ...
    return foo(...)

I also understand that, as a special case, the function can still be rewritten if the recursive call is wrapped in a call to cons.

foo(...):
    # ...
    return (..., foo(...))

What property of cons allows this?  What functions other than cons can wrap a recursive tail call without destroying our ability to rewrite it iteratively?

GCC (but not Clang) is able to optimize this example of "tail recursion modulo multiplication," but it's unclear what mechanism allows it to discover this or how it makes its transformations.

pow(x, n):
    if n == 0: return 1
    else if n == 1: return x
    else: return x * pow(x, n-1)

While GCC likely uses ad-hoc rules, you can derive them in the following way. I'll use pow to illustrate since you're foo is so vaguely defined. Also, foo might best be understood as an instance of last-call optimization with respect to single-assignment variables as the language Oz has and as discussed in Concepts, Techniques, and Models of Computer Programming. The benefit of using single-assignment variables is it allows remaining within a declarative programming paradigm. Essentially, you can have each field of the struct foo returns represented by single-assignment variables that are then passed to foo as additional arguments. foo then becomes a tail-recursive void returning function. No particular cleverness is needed for this.

Returning to pow, first, transform into continuation passing style. pow becomes:

pow(x, n):
    return pow2(x, n, x => x)

pow2(x, n, k):
    if n == 0: return k(1)
    else if n == 1: return k(x)
    else: return pow2(x, n-1, y => k(x*y))

All calls are tail calls now. However, the control stack has been moved into the captured environments in the closures representing the continuations.

Next, defunctionalize the continuations. Since there is only one recursive call, the resulting data structure representing the defunctionalized continuations is a list. We get:

pow(x, n):
    return pow2(x, n, Nil)

pow2(x, n, k):
    if n == 0: return applyPow(k, 1)
    else if n == 1: return applyPow(k, x)
    else: return pow2(x, n-1, Cons(x, k))

applyPow(k, acc):
    match k with:
        case Nil: return acc
        case Cons(x, k):
            return applyPow(k, x*acc)

What applyPow(k, acc) does is take a list, i.e. free monoid, like k=Cons(x, Cons(x, Cons(x, Nil))) and make it into x*(x*(x*acc)). But since * is associative and generally forms a monoid with unit 1, we can reassociate this into ((x*x)*x)*acc, and, for simplicity, tack a 1 on to start, producing (((1*x)*x)*x)*acc. The key thing is that we can actually partially compute the result even before we have acc. That means instead of passing k around as a list which is essentially some incomplete "syntax" that we'll "interpret" at the end, we can "interpret" it as we go. The upshot is that we can replace Nil with the unit of the monoid, 1 in this case, and Cons with the operation of the monoid, *, and now k represents the "running product". applyPow(k, acc) then becomes just k*acc which we can inline back into pow2 and simplify producing:

pow(x, n):
    return pow2(x, n, 1)

pow2(x, n, k):
    if n == 0: return k
    else if n == 1: return k*x
    else: return pow2(x, n-1, k*x)

A tail-recursive, accumulator-passing style version of the original pow.

Of course, I'm not saying GCC does all this reasoning at compile-time. I don't know what logic GCC uses. My point is simply having done this reasoning once, it's relatively easy to recognize the pattern and immediately translate the original source code into this final form. However, the CPS transform and defunctionalization transform are completely general and mechanical. From there fusion, deforestation, or supercompilation techniques could be used to attempt to eliminate the reified continuations. The speculative transformations could be thrown away if it is not possible to eliminate all the allocation of the reified continuations. I suspect, though, that that would be too expensive to do all the time, in full generality, hence more ad-hoc approaches.

If you want to get ridiculous, you can check out the paper Recycling Continuations which also uses CPS and representations of continuations as data, but does something similar to but different to tail-recursion-modulo-cons. This describes how you might produce pointer-reversing algorithms by transformation.

This pattern of CPS transforming and defunctionalizing is a quite powerful tool for understanding, and is used to good effect in a series of papers I list here.


Widest path algorithm steps I need to compute the bottleneck shortest paths from s to all vertices of a graph by modifying the Dijkstra’s algorithm. I found this explanation on Wikipedia(Link to Wikipedia) but I would appreciate if you can elaborate it a bit for me.

  If the edges are sorted by their weights, then a modified version of
  Dijkstra's algorithm can compute the bottlenecks between a designated
  start vertex and every other vertex in the graph, in linear time. The
  key idea behind the speedup over a conventional version of Dijkstra's
  algorithm is that the sequence of bottleneck distances to each vertex,
  in the order that the vertices are considered by this algorithm, is a
  monotonic subsequence of the sorted sequence of edge weights;
  therefore, the priority queue of Dijkstra's algorithm can be replaced
  by an array indexed by the numbers from 1 to m (the number of edges in
  the graph), where array cell i contains the vertices whose bottleneck
  distance is the weight of the edge with position i in the sorted
  order. This method allows the widest path problem to be solved as
  quickly as sorting; for instance, if the edge weights are represented
  as integers, then the time bounds for integer sorting a list of m
  integers would apply also to this problem

So I need to sort my vertex by weight starting from A? I would appreciate if you can explain me the steps in this algorithm.

Thanks

The way to use Dijkstra's algorithm to solve the $s$-to-$t$ widest-path problem (in a directed graph) is described well in the following lecture notes:

http://www.cs.cmu.edu/~avrim/451f08/lectures/lect1007.pdf

Make sure to read Sections 13.1, 13.2, and 13.3.  You will see that a single-line change to Dijkstra's algorithm suffices (we change the $+$ to $\min$, and change the $\min$ to $\max$, to represent the fact that we now have a different metric for the "goodness" of a path).

The section you quoted from Wikipedia is talking about a small optimization to this variant of Dijkstra's algorithm.  However, you can use the variant of Dijkstra's algorithm in Section 13.3 of those lecture notes directly, without the optimization mentioned in Wikipedia, if you like -- and that's easier to understand.


Extracting intersecting objects of the same colour from an image What is the good way to extract the objects(circles) from image as shown in picture below?

respectively create two images one with lines and one with circles from source image.

I started with detecting contours in image to filter everything that may be circle from image which gives me results like this:

I'm new to computer vision and dealing with this specific task, so want thank you for any help and guidance.

Thank you all, here are some answers to questions from comments:

  Define "best"

a good way to do it

  Which techniques do you know that have something like that?

Today I looked at template matching, created a template for the black and white circle and localised them in an original image.
Once I have this extracting lines is straightforward (just subtracting circles from the original image).
This seems working well in the simplest scenario when circles are the same size as templates.

The more robust way I think will be to use Haar Cascade classifier, train it on different size circles, and continue as with results from template matching.

Correct me if there maybe a better way?

The main idea is to digitalize diagrams consisting of black and white circles connected by lines,
The size of diagrams and quality of images may vary. Also, the circles may contain numbers (Extracting those is something for future)

The lines connecting circles are axis aligned, they define position of circles in diagram (similar to cartesian plane)

I mentioned Python (js) and OpenCV languages in case there are some specific implementation details I should be aware of. I'm also learning Python while doing this :).

I don't expect the solution or code, rather pushing to right direction and strategy to deal with this kind of problems.

First, I would suggest you to take a look at morphological operations on images, especially dilation and erosion. Dilation grows the boundary of foreground pixels (gets rid of holes), and erosion shrinks the boundary of foreground pixels (gets rid of bridges). In your case, erosion with an appropriate kernel might get rid of those unwanted lines. Then you apply dilation with the same kernel to preserve the circles. The two of them applied together in this order is called opening. Those functions are predefined in OpenCV, check out morphologyEx function.

Second, I would suggest you to take a look at convexity of shapes. The output circles in your images are convex, but the ones with lines are now. Thus, you can find the non-convex points of the contours (that you already found), and connect the contours from those points, so that you have convex shapes, i.e. desired output circles. To accomplish this, you can find the convex hull and convexity defects using related OpenCV functions.


What happens after the accept state if there are still letters in the string in a Turing machine? Lets say there is a turing machine $M$ where
\begin{align*}
M &= (Q, \Sigma, \Gamma, \delta, q_1, q_{accept}, q_{reject}) \\
Q &= \{q_1, q_2, q_3, q_{accept}, q_{reject} \} \\
Σ &= \{0, 1\} \\
Γ &= \{0, 1, U\}
\end{align*}

with transition functions
\begin{align*}
\delta (q_1, U) &= (q_1, U, R)\\
\delta (q_1, 0) &= (q_1, 0, R)\\
\delta (q_1, 1) &= (q_2, 1, R)\\
\delta (q_2, U) &= (q_{accept}, U, R)\\
\delta (q_2, 0) &= (q_3, 0, R)\\
\delta (q_2, 1) &= (q_2, 1, R)\\
\delta (q_3, U) &= (q_3, U, R)\\
\delta (q_3, 0) &= (q_3, 0, R)\\
\delta (q_3, 1) &= (q_3, 1, R)
\end{align*}

If I input a string and it reaches the $q_{accept}$ state while there are still letters remaining in the string, would it count as accepting the string, rejecting the string, something else?

In the nominal TM definition, the machine is a 7-tuple, $M=(Q,\Sigma,\Gamma,b,\delta,q_0,F)$, where $F$ denotes a set of final states. Wheneven the TM transitions to a state in $F$ it immediately halts, no matter what it did or didn't do beforehand.

From the way you wrote your TM, I believe you meant that your final states are $F=\{q_{accept},q_{reject}\}$, thus once one of them is reached, the TM halts.

Once the above is clear, there is the question of "what happens if the input string isn't fully consumed". Well, this question is a bit misleading, since it implies that the TM consumes the input string symbol-by-symbol (like a DFA or PDA), which is not the case for the nominal TM.

In a Turing machine, the input string appears on the tape at the start of the computation. It is fully there, and needs not be "consumed". Besides of the input string, the tape is empty, i.e., it contains the blank $b$ symbol (where $b\in \Gamma \setminus \Sigma$, so the input cannot contain blanks). Since the input is already there on the tape, there is no question of "consuming" it. The alternative question is reading the input - it is perfectly fine if the TM moves to a final state ($q\in F$) before "reading" the entire input, i.e, when the head of the TM never visits all the tape slots in which the input resides. Again, this is perfectly allowed.

A Note: Sometimes the input is given on a separate tape (which is usually, a read-only tape). This helps to count the memory actually used for processing the computation without counting the space used to hold the input. Such machines are especially relevant for computations that take sub-linear space. Yet again, the machine is allowed to terminate without reading the entire input.


How do we formally regard a function that takes a lookup set as a parameter? I have a function that takes a set as a parameter.  The function $\phi$ maps a general $x \in R$, where $R$ is a commutative ring with $1$, to a $\phi(x) \in \Bbb{N}$ representing the "grammar size" of $x$.  $R$ one-to-one represents grammars generating a single string $s \in \Sigma^*$.

$$
\phi(x, A) = \begin{cases}
0, \text{ if } x \in A \\
|x_t^*| + n(x) - \sum\limits_{i=1}^{n(x)} \phi(x_i, A), \text{ if } x \notin A, \text{ and, } \\
\text{ also ensure, } A := A \cup x
\end{cases}
$$

So as you can see the value of successive calls to $\phi$ depend on the contents of the set $A$.  $A$ is passed-by-reference (not by value copy).

Was wondering if math has a formalism for dealing with such functions that depend on a persistent set parameter.

It's true that if we let $|0^*| = |\epsilon| = 0$ that the size of a grammar $x + y$, for $xy = 0$ (empty intersection), is
$$\psi(x + y) = |s| - \phi(x + y, \{\}) = \\
(\text{init } A:=\{\})\\
|s| - (\phi(x, A) + \phi(y, A))$$.

So that $\phi(z, A)$ acts a like a measure for disjoint elements $xy = 0$ of $R$.  But as you know, measure functions don't usually take a lookup set as a parameter.  So was wondering about the best formalization.

Your $\phi$ is stateful; the value of $\phi(x,A)$ depends on what parameters you have previously evaluated it with.  As such, it is not a mathematical function.  Mathematical functions are stateless.

Formalization serves a purpose: to describe clearly and precisely.  It's not to blindly follow rules, but to serve as an aid to communication.  As long as you have described what you want clearly and precisely,  in a way that a reader is likely to understand, you are good.  So, don't call $\phi$ a function, as that will confuse readers; but you can describe the intended semantics of what you want the procedure $\phi$ to return, in terms of its parameters and its state.


number of connected subgraphs of $G$ with at most $ k>0$ vertices Suppose we have an undirected graph $G=(V,E)$ with $n$ vertices and with max degree of $d>0$.

I need to prove that number of connected subgraphs of $G$ with at most $n\geq k>0$ vertices is $M\leq n\cdot d^{2k}$

My approach was by induction.

For $k=1$ it is true

Suppose we want to prove it for $k=n$ .

let's take any vertice $v\in V$ and run $DFS(v)$ So we will get at most $ d\cdot d^{k-1} \le d^k$ connected commponents.

And because we can take any $ v \in V$ we get that the number of connected subgraphs of $G$ with at most $ k>0$ vertices is $n\cdot d^{k}< n\cdot d^{2k}$

Now my question is:
Am I right with my approach?
Is there any other solution for this problem?

I really didn't understand why they gave me this upper bound...

Your argument doesn't really constitute a proof, so it is hard to evaluate it. It's not really clear where the maximum degree comes in. You write the inequality $d \cdot d^{k-1} \leq d^k$, but it isn't clear why we're multiply $d$ by $d^{k-1}$. It's not clear why DFS is relevant here (and why you mention connected components when you're interested in connected sub graphs), and it's not clear how you use the inductive hypothesis.

Here is a different argument which hopefully functions better as a proof. Before we can start the proof, we need to understand what we are trying to prove.

Definition. Let $G = (V,E)$ be a graph. An induced subgraph of $G$ is a graph of the form $(U, E \cap U \times U)$ for any non-empty $U \subseteq V$. A connected subgraph of $G$ is an induced subgraph of $G$ which is a connected graph.

Instead of connecting connected subgraphs directly, it is better to count trees instead. We can do this because every connected graph has a spanning tree. This is embodied in the following lemma.

Lemma 1. Let $G$ be a graph on $n$ vertices, and let $1 \leq k \leq n$. The number of connected subgraphs of $G$ having $k$ vertices is at most the number of trees of $k$ vertices contained in $G$. (A tree is contained in $G$ if all the edges of the tree are edges of $G$.)

Proof. Let $C_k$ be the set of connected subgraphs of $G$ having $k$ vertices, and let $T_k$ be the set of trees of $k$ vertices contained in $G$. Since each connected graph has a spanning tree, we can identify a tree of $k$ vertices inside each subgraph in $C_k$. This gives an injective function $f\colon C_k \to T_k$: if $f(c) = t$ and $t$ is a tree on the vertex set $U$, then $c$ is the subgraph induced by $U$. Therefore $|C_k| \leq |T_k|$. $\quad \square$

We can estimate the number of trees of size $k$ contained in $G$ using an appropriate encoding scheme. The basic idea is to pick a starting vertex inside the tree, describe the vertices adjacent to it in the tree, and so on. Each time we describe the adjacent vertices, we can use the fact that every vertex has at most $d$ neighbors.

Lemma 2. Let $G$ be a graph on $n$ vertices of maximum degree $d$. The number of trees of $k$ vertices contained in $G$ is at most $nd^{2k-2}$.

Proof. The lemma clearly holds for $k=1$, so suppose that $k \geq 2$.
Fix an arbitrary ordering on the vertices of $G$. We describe a procedure that receives as input a tree $T$ and a leaf $v$, and outputs a succinct numerical encoding of $T$. The procedure, Encode, uses a subroutine, Encode-child, which accepts $T$, a vertex $u \in T$, and another vertex $p$ which is adjacent to $u$ in the tree $T$.

Encode(T, v):
  Let u be the unique neighbor of v in T.
  Suppose that u is the i'th smallest neighbor of v in G.
  Output v, i, and run Encode-child(T, u, v).

Encode-child(T, u, p):
  Let u_1, ..., u_m be the neighbors of u in T other than p.
  Output the degree of u in T, i.e., m+1.
  For i = 1, ..., m:
    Suppose that u_i is the j'th smallest neighbor of u in G.
    Output j, and run Encode-child(T, u_i, u).

(We assume that $i$ in Encode and $j$ in Encode-child run from $1$ to $d$.)

What does the output look like? The first item in the sequence is a vertex, which we can identify as a number from $1$ to $n$ (using the order of the vertices of $G$). All other items are numbers from $1$ to $d$. Thinking of $T$ as rooted at the starting leaf $v$, for each non-root vertex we encode both its degree and its index as a child of its parent, for a total of $2(d-1)$ numbers.

We can reconstruct the tree from this encoding. Indeed, it is not difficult to explicitly spell out a decoding procedure which gets as input the sequence of $1+2(d-1)$ numbers, and outputs a tree. It is more challenging to prove that if we encode a tree $T$ and run the decoding procedure, then we get back the tree $T$; however, the challenge is mostly technical rather than conceptual, since intuitively it is clear that the decoding algorithm works. We therefore leave these steps to the curious reader.

We conclude that the encoding procedure described above is an injective mapping from the set of pairs $(T,v)$, where $T$ is a tree of $k$ vertices contained in $G$ and $v$ is a leaf of $T$, to the set of sequences lying in $[n] \times [d]^{2k-2}$ (where $[m] := \{1,\ldots,m\}$). Since every tree contains a leaf, this shows that the number of trees is at most $nd^{2k-2}$ (in fact, since every tree contains at least two leaves, we can improve this to $nd^{2k-2}/2$). $\quad\square$

As a conclusion, we can estimate from above the number of trees having at most $k$ vertices by
$$
\sum_{\ell=1}^k nd^{2\ell-2} = \frac{nd^{2k}-n}{d^2-1} \leq nd^{2k}.
$$
According to Lemma 1, this is also an upper bound on the number of connected subgraphs having $k$ vertices.

Is this bound tight? Probably not. Our encoding scheme is quite wasteful. For example, when encoding $j$ in Encode-child, we can use a number from $1$ to $d-1$, since we know that $u_i \neq p$. This improves the exponent to $d(d-1)$ from $d^2$.

In order to determine the optimal exponent, we can take as our graph $G$ the infinite $d$-ary tree, and count the number of trees of $k$ vertices rooted at a fixed vertex of $G$.
This is worked out in this math.se question, which shows that the optimal exponent is $(d-1)^{d-1}/(d-2)^{d-2}$. For example, when $d=3$ the optimal exponent is $4$ rather than $6$ (the well-known asymptotic of Catalan numbers), and when $d=4$ it is $6.75$ rather than $12$.


Minimal DFA that accepts binary strings whose decimal equivalent is divisible by 32 I thought the answer would be 32 for remainder $0,1,2,\dots, 31$. But answer given as $6$.
and explanation is given as if the number is $2^n$ then number of states required would be $n+1$.

Binary numbers that are divisible by 32 are ending in zero's. You can just keep track of how many consecutive zero's we have seen. If you want to answer the same question for the decimal alphabet, yes, then you need to worry about remainders modulo 32. The phrase "decimal equivalent" is a bit confusing here: divisibility of a number does not change when choosing another representation.

After building the automaton you can minimize it using standard constructions, to see if you cannot do with less states. Perhaps the same approach works for $2^n$, but then you not have a single "concrete" automaton. Alternatively you might use the theory of Myhill-Nerode equivalence classes of the language, to show the number of states is at least a certain number.


Proof of big theta using induction Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants.

$T(n) = a$, if $n = 2$

$T(n) = 2T(n/2) + cn$ if $n > 2$
Use induction to prove that $T(n) = \Theta(n \log n)$

Any idea on how to solve this?

Hint: If $T(n/2) \leq M \frac{n}{2} \log \frac{n}{2}$ then
$$ T(n) = 2T(n/2) + cn \leq Mn\log \frac{n}{2} + cn \leq Mn\log n +n (c-M\log 2). $$
The lower bound should be similar.


Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system? Just what the title says.
Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system (without a single point of failure)?

My current thoughts are that this is a consensus problem, and is thus impossible to achieve in an asynchronous messaging system (like the Internet). Another way I look at it is that if we could generate such a sequence in a distributed system, then the problem of total ordering is solved.

Please correct me if I'm wrong.

You're right that this is an impossible problem to solve in an asynchronous distributed system, and you're also right that it would solve a lot of problems if we could get a totally ordered clock. But it only solves "all" our problems if the clock has the additional constraint of a meaningful relationship with real time.

The two best solutions we have are partial ordering (Lamport clocks) and consensus (which can be fault tolerant but is typically driven by an elected leader). The latter provides total order and works well in practice (with randomized timers), but is impossible to guarantee in theory (FLP).


Geometric median of two disjoint sets of points lies on line between their respective medians I was working on a problem about geometric medians and I had an idea for a divide and conquer solution, but it would only work if a set of points, when split into two disjoint sets, and those sets respective geometric medians calculated and a line passed between, it holds that the geometric median of the overall set of points lies on that line. When graphing it and visualizing it, seems possible, and when I used existing algorithms and experimented, it seems to be very close but not quite on the same line. I am not sure if this is due to error in calculation of the geometric median or not.

I have some example Python code demonstrating how close the numbers are here: Geometric Median comparison

Any expertise in this matter would be appreciated.

If $A$ and $B$ are two set of points, the geometric median of $A \cup B$ does not necessarily lie on the line passing between the geometric mean of A and the geometric mean of $B$.

In the following example the points of $A$ are red and the one in $B$ is blue. The geometric median of $A$ is the red square. The green line connects the geometric means of $A$ and $B$. The black square is the geometric mean of $A \cup B$, i.e., the Fermat point of the triangle whose vertices are in $A \cup B$.


Distance k-Dominating Set on a Tree I don't consider myself very good at math, but nevertheless I enjoy solving optimization problems like the ones often asked in ACM ICPC (a college programming competition). I recently came across an issue while trying to solve one of such problems. I'd appreciate any help to find a linear algorithm (something better than $O(n^2)$ is still OK) for the following problem:

  Given a tree $T = (V,E)$ we want to find the size of the smallest set $V'$ such that $V'$ is a subset of $V$ and for every vertex $u$ in $V$ there's at least one vertex $w$ in $V'$ such that $\text{dist}(u,w)$ is less than or equal to $K$, where $K$ is a given natural number.

Here, note that $\text{dist}(u,w)$ is the length of the shortest path from $u$ to $w$ in the tree (in terms of hops), and tree $T$ is unweighted.

I'm very aware that there is a known greedy algorithm for $K=1$, which is in fact the cardinality of the minimum vertex cover. Solving for a general $K$ is what I'm interested in. I thought about several approaches but none of them seem to convince me. Do any of you know how to approach this?

Binary, rooted trees

Let's focus first on the case of binary, rooted trees
(i.e., every vertex has either 0 or 2 children).
This case can be solved in polynomial time using
dynamic programming, with subproblems as defined below.

Let me first define some notation that will be helpful.
$\newcommand{\dist}{\text{dist}} \newcommand{\dom}{\text{dom}} \newcommand{\gap}{\text{gap}} \newcommand{Ni}{\mathbb{N}_{-\infty}}$
Let $T_v$ denote the set of descendants of $v$, including $v$ itself, i.e., the vertices in the subtree rooted at $v$.  If $S$ is a set of vertices, let $\dist(v,S)= \min \{\dist(v,s) : s \in S\}$.  Define $\dom(S) = \{v\in V : \exists s \in S . \dist(s,v) \le K\}$; this is the set of vertices dominated by $S$.
Finally, let $\gap_v(S) = \max \{\dist(v,w) : w \in T_v \setminus \dom(S)\}$, i.e., the gap of $S$
(with respect to $v$) is the depth of the deepest descendant of $v$ that is not
dominated by some node of $S$.
Also, define the depth of $S$ (with respect to $v$) to be $\dist(v,S)$.
Define $\Ni = \mathbb{N} \cup \{-\infty\} = \{-\infty,0,1,2,3,\dots\}$.

The intuition is that we can build up an optimal dominating set
recursively, bottom-up.
Let $v_0$ and $v_1$ be the two children of the root, and suppose we have
a set $S_0 \subseteq T_{v_0}$ for the left subtree and $S_1 \subseteq T_{v_1}$
for the right subtree.
Can we combine $S_0,S_1$ somehow to get a dominating set for the whole tree?
To determine the answer to this question, all we need to know about
$S_0,S_1$ are their depth and gap (with respect to the root).
Therefore, all that matters when searching for a minimum dominating set
is their depth, gap, and size.
We don't need to enumerate all possibilities for $S_0,S_1$; for each
possible combination of depth and gap, we just need to know the minimum
attainable size for a set with that depth and gap.
This enables us to use dynamic programming effectively.

In particular, we will use the following definition of a subproblem:

  INPUT: a vertex $v \in V$, a depth $d \in \Ni$, a gap $g \in \Ni$
  OUTPUT: $n(v,d,g)$, defined to be the size of the smallest set $S \subseteq T_v$ of depth $d$ and gap $g$, i.e., the size of the smallest set $S \subseteq T_v$ such that $\dist(v,S)=d$ and $\gap_v(S)=g$

You can use dynamic programming to solve these subproblems,
traversing the tree in a bottom-up fashion.
If $v$ is a leaf, $n(v,d,g)$ is easy to compute.
Next suppose that $v$ is an internal node, with children $w,x$.
Then we can compute $n(v,d,g)$ from $n(w,\cdot,\cdot)$ and $n(x,\cdot,\cdot)$
as follows.
If $d>0$ and $g\ge 0$, we use the recurrences:

$$n(v,0,-\infty) = \min \{1 + n(w,d',g') + n(x,d'',g'')\}$$

$$n(v,d,-\infty) = \min \{n(w,d-1,-\infty) + n(x,d'',g''), \\
n(w,d'',g'') + n(x,d-1,-\infty) : d'' \ge d-1, d+g''+1 \le K\}.$$

$$n(v,d,g) = \min \{n(w,d',g') + n(x,d'',g'') :
\min(d',d'')=d-1, \max(g',g'')=g+1\}.$$

We have some easy base cases when $d\le 0$ or $g=-\infty$:
$n(v,-\infty,g) = 0$ if $g = \max\{\dist(v,w) : w \in T_v\}$,
or $\infty$ otherwise;
$n(v,0,g) = \infty$ if $g \ge 0$.

In the exposition above, $d,g$ are implicitly subject to the constraints that
$d \in \{-\infty,0,1,\dots,2K\}$, $g \in \{-\infty,0,1,\dots,K-1\}$,
$d \ge 0 \land g \ge 0 \implies d+g > K$, $g \ge 0 \implies d \le g+K+1$,
$g=-\infty \implies d \le K$ (since other combinations aren't possible).
$d',g'$ and $d'',g''$ are implicitly constrained in the same way.

Finally, the size of the smallest distance-$K$ dominating set for the entire tree is given by
$\max \{n(r,d,-\infty)\}$ where $r$ is the root of the tree.

Running time analysis:
There are $O(|V| \cdot K^2)$ subproblems.
Each recurrence can be computed in $O(K^2)$ time, by organizing the
$\min$ computation suitably.
Therefore, the total running time is $O(|V| \cdot K^4)$.

Unrooted trees

It is easy to deal with unrooted trees:
simply pick an arbitrary vertex to be the root, and now a depth-first
search will turn it into a rooted tree.
Then you can apply the above algorithm.

Trees of arbitrary branching factor

The above algorithm can be easily generalized to trees whose
branching factor at each vertex is $\le 2$ (i.e., each vertex has
either 0, 1, or 2 children).

I haven't thought through what happens if the tree might have
arbitrary branching factor (i.e., not restricted to $\le 2$).
I expect that similar recurrences and subproblems will be applicable.
If you organize the $\min$ computations cleverly, you might be able
to achieve a low-order-polynomial running time,
e.g., $O(|V| \cdot K^c)$ for some small constant $c$ (e.g., $c=4$).
However, I haven't worked through the details; I'll leave that to you.