Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n The questions is to find the running time $T(n)$ of the following function:

$$T(n)=3\cdot T(n/2) + n \tag{1}$$

I know how to solve it using Master theorem for Divide and Conquer but I am trying to solve it by expanding:
$$\textstyle
T(n) =  n+\frac{3}{2}n +(\frac{3}{2})^2n + (\frac{3}{2})^3n + \cdots
\tag{2}$$
which implies
$$T(n)=n\sum_{k=1}^{n}({\textstyle \frac{3}{2}})^{k-1} \tag{3}$$
and so
$$T(n)=2n\cdot(({\textstyle\frac{3}{2}})^n-1) \tag{4}$$

The right answer to this problem is $\Theta(n^{\log3})$.
How can I reach to right answer through my approach as shown above.Is my approach wrong ? How can I solve it without using Master theorem.

Any help is appreciated.

You have a mistake going from (2) to (3) because you lost $n$ and it is not clear why your sum should range from $i = 1$ to $i = n$ (it does not). Then it is not clear how you got from (3) to (4) where $n$ reappeared. Perhaps you just los $n$ in (3) but otherwise you had it on paper.

Let us try again:
\begin{align*}
T(n) &= n + (3/2) n + (3/2)^2 n + \cdots
\end{align*}
But when does sum end? (This is what created your mistake.) It ends when we get to the base case, which is $T(1)$. After $k$ unfoldings we have $T(n/2^k)$ so we will reach $T(1)$ when $k = \log_2 n$. Thus, we continue like this:
\begin{align*}
T(n) &= n + (3/2) n + (3/2)^2 n + \cdots + (3/2)^{\log_2 n} T(1) \\
&= \textstyle \sum_{i=0}^{\log_2 n} (3/2)^i n\\
&= n \cdot \textstyle \sum_{i=0}^{\log_2 n} (3/2)^i.
\end{align*}
It remains to add the sum. It is a geometric series, so we can look up the formula $\sum_{i=0}^k a^i = (a^{k+1} - 1)/(a - 1)$ and get
\begin{align*}
{\textstyle \sum_{i=0}^{\log_2 n} (3/2)^i} &=
\frac{(3/2)^{1 +\log_2 n} - 1}{3/2 - 1} \\
&= 2 \cdot ((3/2) \cdot (3/2)^{\log_2 n} - 1) \\
&= 3 \cdot (3/2)^{\log_2 n} - 2 \\
&= 3 \cdot (n^{\log_2 (3/2)}) - 2 \\
&\in \Theta(n^{\log_2 (3/2)}) \approx \Theta(n^{0.58})
\end{align*}
The final result is this sum multiplied with $n$, so it is
$$\Theta(n \cdot n^{\log_2(3/2)}) = \Theta(n^{\log_2 2 + \log_2 (3/2)}) = \Theta(n^{\log_2 3}),$$
assuming I can still do logarithms....


Why must a Primary Index be sparse? Reading Fundamentals of Database Systems 7th Edition, on Page 603, it says,

  Indexes can also be characterized as dense or sparse. A dense index has an index entry for every search key value (and hence every record) in the data file. A sparse (or nondense) index, on the other hand, has index entries for only some of the search values. A sparse index has fewer entries than the number of records in the file. Thus, a primary index is a nondense (sparse) index, since it includes an entry for each disk block of the data file and the keys of its anchor record rather
  than for every search value (or every record).

Is that true though? As far as a database is concerned, if there are no sparse-indexes provided, is it said that all data-files have no "primary index"? I get that a specific designation for a sparse unique index on a block may be required, but is that what primary means? What does this mean for a database, like PostgreSQL, that implements Primary Keys on a dense btrees, and stores its rows in an unordered heap? Does it, technically, not have a "Primary Index"?

Without the context of the excerpt, I found it confusing since it seemed to depend on fairly specific implementation details. This is, in fact, the case. These course notes give a decent overview of this and related terminology.

A primary index refers to an index stored in sorted order on the sorting key of data stored in blocks. To look up a value, you do a binary search on the index which will produce a pointer to the block, and then you can do a binary search on the data in the block. If the data wasn't in blocks, there would be no point to this as you could just do binary search directly on the data file. (With a primary index, while the contents of the blocks need to be in sorted order, the blocks themselves don't necessarily need to be.) This index is not dense since it stores a pointer to a block which will typically contain multiple records, so there is not a one-to-one correspondence between index entries and records.

If you wanted to lookup data based on a key that the records are not sorted on, then you couldn't rely on records between index entries being in the same block, thus an index entry would be required for each specific record. This would be a dense index.

So the thing to note is that this terminology is referring to a specific way of storing and indexing data, namely as a collection of sorted blocks. "Primary index" has nothing to do with "primary key" in this terminology. A primary index depends on how the data is actually sorted (assuming it is sorted) which doesn't at all need to be based on the primary key, e.g. you may sort by a timestamp. There is no need for a "primary index" to exist at all.

A B-tree (and its variations) is just a different indexing approach entirely. You can still potentially apply the "dense index"/"sparse index" terminology to it. For example, if your data is sorted on the key the B-tree index is indexing, then it could just as well store only pointers to blocks and then perform a binary search within the block once fetched. This arrangement would produce a sparse index. You could easily imagine different arrangements that would produce a B-tree index that is dense.

I think you are viewing "primary index" as being more widely applicable than it is. I know I was at first which was the source of my confusion. In the context in which it applies, it is a reasonable term, but "primary index" is way too uninformative to stand alone.


Is TD-learning considered a model-based algorithm? Differently from Sarsa and Q-learning, pure temporal difference learning (TD-learning) works with state value functions $V(s)$ and not state-action Q value functions $Q(s,a)$. It means that, in order to select the best action at state $s$, the resulting state $s'$ for every possible action must be computed, so we can get $V(s')$. Thus, we need a model for computing $s'$ from a $(s,a)$ pair. Is that correct? Does that mean that TD-learning can be considered a model-based technique? Or in the case of TD-learning we consider it just a value updating algorithm and ignore the control part, thus removing the need for a model?

The previous answer is wrong. TD-learning is a model-free algorithm.

You compute $V_{\pi}(s)$ for a fixed policy $\pi$, then you update your policy based on $V$ a la policy iteration.

Source: https://webdocs.cs.ualberta.ca/~sutton/book/ebook/node60.html


Relative order of values and weights in Knapsack In knapsack problem, we have some items with some values and weights. We also have a knapsack with a specific capacity, and we intend to fill the knapsack with these items. The main objective of this problem is to maximize the value of items in the knapsack.

Knapsack can contain maximum 11 kg items

item1: value(1) weight(1 kg)

item2: value(6) weight(2 kg)

item3: value(18) weight(5 kg)

item4: value(22) weight(6 kg)

item5: value(28) weight(7 kg)

Are the items also sorted by their weights when we sort them by their values ?

In other words, are the weights parallel with the values ?

For example, can the item2 have a value 20 but its weight is equal to 2 kg ?

The weights and values can be arbitrary. In particular, if you sort the items by their weight, then they need not be sorted by their value.

More generally, if you look at a formal definition of the Knapsack problem, you will see that nothing is mentioned about the possible weights and values of the items (beyond their being positive integers). Every instance which conforms to the definition is valid.

In other words, you should be able to answer such questions by looking at the formal definition of the problem. There is no hidden information which can only be obtained by asking questions on forums. Indeed, it is exactly the opposite — the problem statement defines the problem completely.


Lower bounds and $P$ vs $NP$ I know $P$ vs $NP$ is an open problem in Computer Science. However the people concerned (at least according to Wikipedia) believe $P \neq NP$.

I have two questions:

$(1.)$ Given that it is possible to prove lower bounds for problems. Does there exist any problem(s) for which the solution can be verified in polynomial time but no known algorithm can solve it in polynomial time which has a proven lower bound?

$(2.)$ Is this proven lower bound polynomial or exponential?

Every $NP$-complete problem is an example of this! It's just a question of how good the lower bounds are.

For example, there's an $\Omega(n)$ lower bound on basically every problem, since you need to read your entire input to solve it. This is a very imprecise lower bound, but it does exist.

So, you're not going to get a good list of a bunch of problems like this, because such a list would be too large, and uninformative.

Whether there are problems with notable lower bounds is a different issue. I don't know of any that fit your criteria (sorting is the most famous one, but it's in $P$). Here's an example question about bounds on 3SAT:

https://cstheory.stackexchange.com/questions/93/what-are-the-best-current-lower-bounds-on-3sat

Not very informative, as you can see.
The known lower bounds in such a case will always be polynomial. If there were any problems verifiable in polynomial time (in $NP$) with an exponential lower bound, that would imply that $P \neq NP$.


Minimum bottleneck path between two vertices in an undirected graph I have an undirected graph, where the value of the path is the maximum weight among all weights
edges included in it. And I want find the path of minimum value between two  given vertices in time $O(n + m)$, where $n$ - number of vertices, $m$ - number of edges.

I will use the fact that you can check for the connectivity between two vertices $s$ and $t$ in a graph with $m>0$ edges in time $O(m)$.

Call $G$ be the input graph, and let $s$ and $t$ be endpoints of the paths you are interested in. I will denote by $G_w$ (resp. $G^<_w$) the graph induced by all the edges of weight at most (resp. less than) $w$ in $G$. You can solve the problem using the following recursive algorithm:

If $G$ has no edges, report that $s$ and $t$ are disconnected in $G$.

If $G$ has at least one edge, find the median $w$ among the edge weights of $G$, and proceed as follows:

If  $s$ and $t$ are connected in $G_w$ and disconnected in $G^<_w$, return $w$.
If $s$ and $t$ are connected in both $G_w$ and $G^<_w$, apply the algorithm recursively on $G^<_w$ (notice that $G^<_w$ has at most $\frac{m}{2}$ edges).
If $s$ and $t$ are disconnected in $G_w$, build the graph $G'$ obtained from $G$ by
identifying all vertices that belong to the same connected component of $G_w$, and apply the algorithm recursively on $G'$ (notice that $G'$ has at most $\frac{m}{2}$ edges, since it can't contain any edge with weight less than or equal to $w$).

The time complexity of the above algorithm is described by the recurrence equation:
$T(m) = T(m/2) + O(m)$, which has solution $T(m)=O(m)$.

This problem is the same as its maximization version once all edge weights are multiplied by $-1$.


Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers? I am experimenting with the sorting of arrays and their execution times.
While using bubblesort, insertsort and quicksort, I have observed that relative standard deviation (%RSD) of execution times, for five hundred arrays of the same size containing random integers, decreases if the size of the arrays increases.

For example: if the %RSD of execution times while sorting 500 arrays, of size fifty elements each, is observed as 7%, the same for arrays with five hundred elements each is about 2.5%.

So the question is: why this value of change decreases with the increase in the array size?

P.S. I am using a cycle-accurate simulator (gem5) and taking exact clock cycles.

In the case of insertsort, the complexity (time) depends on the number of swaps performed during sorting. A kth element (k=1,2,3,...,n) in an array of size n, may require 0 to k swappings.

The execution time mentioned in the question depends on the sum of all the swaps performed during the sorting of a complete array.

Considering the random initialization of the arrays, the number of swaps performed for any kth element would be a random number bounded by the given range.

Now, If we consider the average value of the number of swaps per element (sum of all the swaps divided by the number of elements in the array), then, according to the law of large numbers, as the number of elements per array will increase this average will get closer to the expected value.

i.e., the variation in, the total number of swaps per array, among different arrays, will decrease.

Hence, the change (%RSD) in the execution times will also decrease.

--to be continued--


Regular language as finite union of periodic sets Is it true that every regular language can be expressed as a finite union of periodic sets?  In other words, if $L$ is regular, then do there exist finite sets $A_1,\dots,A_n,B_1,\dots,B_n$ such that

$$L = A_1 \cdot B_1^* \cup \cdots \cup A_n \cdot B_n^*.$$

I know this is true for regular languages over a unary alphabet, but I'm not sure about general alphabets.

The answer by @YuvalFilmus is perfectly fine, and points you to the import notion of star height. But let me add a little bit more. We will show that languages of your form give a proper subset of the languages of star height one. But first, some musings what might come close to your form.
General Regular Languages
First, probably the closest form to yours for regular $L \subseteq \Sigma^*$, accepted by a complete deterministic automaton $A = (\Sigma, Q, \delta, q_0, F)$.
For $q \in Q$ and $E \subseteq Q$, write $L_{q, E}(A)$ for the language
accepted by $(\Sigma, Q, \delta, q, E)$, i.e., changing the start state to $q$
and the set of final states to $E$.
Then, we can write
$$
 L = \bigcup_{ q \in F } L_{q_0, q}(A) L_{q, \{q\}}(A)^*
$$
This result seems to be folklore and follows easily. A more refined variant of this decomposition appears in the book Automata, Languages and Machines, Volume A by S. Eilenberg, under the name iterated up-decomposition.
Commutative and Bounded Regular Languages
Others forms, more close to yours, and being proper generalizations of the unary language case you mentioned, could be given for the bounded and commutative regular languages. A language is commutative, if it is closed under permutation of letters. For example, $\{ab,ba\}$ is commutative, whereas $\{ab\}$ is not. A language $L \subseteq \Sigma^*$ is bounded, if $L \subseteq w_1^* \cdots w_n^*$
for words $w_i \in \Sigma^*$. In what follows, let us denote by $\diamond$ the shuffle of two languages, and, for $L \subseteq \Sigma^*$, by $L^{\diamond,*} = \bigcup_{n \ge 0} \underbrace{L \diamond \ldots \diamond L}_{\mbox{$n$ times}}$ the iterated shuffle. Also, by $\operatorname{perm} : 2^{\Sigma^*} \to 2^{\Sigma*}$ denote the permutational closure, or commutative closure, i.e. adding all words that are permutations.
For example, $\operatorname{perm}(\{ab\}) = \{ab,ba\}$.
Note that $L \subseteq w^*$ is regular iff  $L = w^n(w^p)^*$ for some $n, p \ge 0$. This is implied by noting that $\{ n : w^n \in L \}$ is ultimately periodic (it could be viewed as a regular unary language).
By a result of Ginsburg/Spanier we have

A language $L \subseteq w_1^* \cdots w_r^*$ is regular iff it is a finite union of languages of the form $L_1 \cdots L_r$, where each $L_i \subseteq w_i^*$ is regular.

Also, if $\Sigma = \{a_1, \ldots, a_k\}$ and $L \subseteq \Sigma^*$ is commutative and regular, it is possible to show that
$$
 L = \bigcup_{i=1}^n \operatorname{perm}(u_i) \diamond \operatorname{perm}(N_i)^{\diamond,*}
$$
for finite sets $N_i \subseteq a_1^* \cup \ldots \cup a_k^*$ with $|N_i \cap a_j^*| \le 1$.
Also, as stated here and here, a regular language $L$ over $\Sigma = \{a_1, \ldots, a_k\}$ is commutative iff
$$
 L = \bigcup_{i=1}^n U_{i,1} \diamond \ldots \diamond U_{i,k}
$$
for unary regular languages $U_{i,j} \subseteq a_j^*$
with $i \in \{1,\ldots, n\}$ and $j \in \{1,\ldots,k\}$.
All these results are closely related. Note that for unary languages, they all reduce to the form you have stated.
A Necessary Condition for Languages of your Form
The condition I will state involves topology and infinite words. It yields, for example, that $b^*a$ and $(b^*a)^*$ could not be written in your form. The latter has star height two, note that star height could be characterized by cycle rank, see Eggan's Theorem.
However, I do want to give a self-contained, and different, argument here, not based on star height. Let $\Sigma^{\omega}$ be the set of infinite words over $\Sigma$. Define an operator $W : 2^{\Sigma^*} \to 2^{\Sigma^{\omega}}$ by, for $L \subseteq \Sigma^*$,
$$
 W(L) = \{ \xi \in \Sigma^{\omega} \mid \mbox{ $\xi$ has infinitely many prefixes in $L$ } \}.
$$
Then
\begin{align*}
 W(b^*a) & = \emptyset \\
 W((b^*a)^*) & = \{ \xi \in \Sigma^{\omega} \mid \mbox{$\xi$ has infinitely many $a$'s. } \}.
\end{align*}
Observe that
$$
 W(U \cup V) = W(U) \cup V(V),
$$
as, if $\xi \in W(U\cup V)$, then, by the pigenhole principle, at least one of $U$ or $V$, or both, must contain infinitely many prefixes of $\xi$. Also, in your form we could assume all the sets $A_i$ are singletons, as concatenation distributes over union.
Let us inspect languages of the form $L = u(u_1 + \ldots + u_n)^*$, which are the parts of your form.
Set $\Gamma = \{ b_1, \ldots, b_n \}$, an auxiliary alphabet, and consider the homomorphism $h : \Gamma \to \Sigma^*$ given by $h(b_i) = u_i$, i.e., substituting each letter by the corresponding word. This homomorphism could also be applied to infinite words in $\Gamma^{\omega}$. We have
$$
 W(u(u_1 + \ldots + u_n)^*) = \{ uh(\xi) \mid \xi \in \Gamma^{\omega} \}.
$$
In particular, if all the set $B_i$ are singletons, $W(L)$ is finite, and $W(L) \ne \emptyset$ for every infinite language of your form.
By the last observation, $b^*a$ could not be written in your form. So, this is a very simple example, even of star height one.
But let us show that $L = (b^*a)^*$ could also not be written that way. Assume it could be, then the set of infinite words, which all have an infinite number of $a$'s in it, could be written in terms of a homomorphism
$h : \Gamma^* \to \Sigma^*$ as outlined above, i.e.,
$$
 \{ \xi \in \Sigma^{\omega} \mid \mbox{$\xi$ has infinitely many $a$'s. } \} = u h(\Gamma^{\omega})
$$
for some $u \in \Sigma^*$.
Let $m = \{ |h(x)| : x \in \Gamma \} + |u|$.
Then $ub^maaaaa\cdots$ is in this language,
and this implies $h(x) \in b^+$ for some $x \in \Gamma$.
But then $ubbbbbbb\cdots \in uh(\Gamma^{\omega})$, which is a contradiction, as it only contains a finite number of $a$'s. Hence, $(b^*a)^*$ could not be written that way. $\square$


Closing shapes at non-endpoints Consider how one would represent the following image in vector graphics:

Pretty simple, right?  The entire shape can be represented by a single path element.

But suppose additionally that you want to color the heart at the top red.  The path element is an open shape, so trying to fill it results in an appropriately red heart but also implementation-dependent bleeding between the spiral endpoints.

Obviously, one could just draw the heart and the spiral tails as separate elements, but then the vector graphics representation no longer mirrors how a human being would draw the same image, and makes it more difficult to manipulate as a single object.  One needs a way to communicate to the computer that two particular path segments within the larger path intersect in such a manner that they close a sub-shape.

Is there a vector graphics format capable of doing this?  More relevantly, how is it implemented and are there any papers on it?

In CAD systems this is done

On user side

find intersection of two curves
split curves by their intersection
make closed path to form a polygon
fill polygon
you can still group separated line into one line and operate with it as previously, change in internal logic (math core side) will be hidden from you

On math core side

choose appropriate method of intersection of curves based on the type of the curves
do intersection either by exact intersection if lines types support this (eg straight lines) or by numerical method (usually iterative) in other cases (eg when you have splines underlying)
create new curves based on existent edges of lines and on the found intersection point
an so on


Write the conjunctive or disjunctive normal form of an expression $f$ Write the conjunctive or disjunctive normal form of an expression $f$ that is true if the number  $t=(xyz)_2$ is a zero of the following polynomial:

$$p(t)=(t-6)(t-5)(t-4)(t-2)t(t+1)(t+3)(t+7)$$

The zeros of this polynomial are $-7,-3,-1,0,2,4,5,6$. So $t$ has to be $(000)_2$ or $(010)_2$ or $(100)_2$ or $(101)_2$ or $(110)_2$ or... But now I don't know how to represent these negative numbers in binary? In other words how do I write $-7,-3,-1$ in the form $(xyz)_2$?

As @DavidRicherby said, it's best if you ask who-gave-you-the-question what he meant by $(xyz)_2$.
But if you absolutely can not do that, then you look at the situation mathematically as...

$(xyz)_2$ here is a set $\{000,001,010,011,...,111\}$ of $8$ elements which forms a ring.
In particular, it supports two binary operation $+$ and $\times$ where both operation has identity element, the addition has inverses...

If you can decide the addition table and multiplication table that makes sense in your context, then you're set.
As long as it's a ring, then that polynomial equation makes sense.


What is the best solving algorithm for a game with stacks? Game Explanation: Suppose there is a game with cards that have numbers from 1 to n. Each card has a different number so there are not two cards with the same number. The deck is scrambled. We chose one card from the deck and we create a stack. Then when we chose the next if the card is a number lower than the top of the stack we add it to the stack. If the card is greater than the top of the stack we create a new stack with this card as the top. As we progress each card we draw from the deck should go either in one of the stacks (if it is less than the top of at least one of them) or create a new stack (if it is greater than the tops of all the stacks). If the card we drew can go to more than one stack it is our choice as to which stack it should go.

Game rule: If there is at least one stack were a card can go, we cannot create
a new stack with this card as the top.

Game Objective: Finish the game (draw all n cards) with the minimum number of stacks.

My solution: Except the first time we draw were we have to create a stack, the next rounds, when we draw a card, we examine the top of each stack and find the minimum top call it M1 . Then if the card can go there (less than M1) we place it there. If it is greater than M1, we place it in the next minimum top we can. That way, we leave the tops that have greater numbers open for new numbers that could be greater than the one we drew this round, thus we minimize the possibility of creating a new stack.

My question: Is my solution correct? If it is, is there any solution better than mine? I think my solution is O(n*m), where n is the number of cards and m the number of stacks. Is there a solution with better complexity?

First Attempt at proving that the algorithm is optimal (based on links provided) :
Let f be the number of stacks and A our algorithm and O an optimal algorithm.
For i=1 card deck: then f(A) <= f(O), they will actually be equal f(A)=f(O), because each algorithm must create a stack with the first card (by rule). If f(A)<=f(O) for i=n then for i=n+1 (I don't know how to prove that f(A)<=f(O) here).

Second Attempt:

My proof: At the base the number of stacks will be equal as I mention above. Then suppose that the state $A^{i-1} \preceq O^{i-1} $ .

This means that the vectors will be the following

$(t_1,\dots,t_k) \prec (u_1,\dots,u_\ell)$ if $k \prec \ell$
$(t_1,\dots,t_k) \prec (t_1, \dots, t_j, u_{j+1}, \dots, u_k)$ if $t_{j+1} \prec u_{j+1}$.

In case number 1 the number of stacks in A is less than or equal to the one of O.
I think it is obvious that if another element (card) was to be added to both of those vectors, the resulting vectors would be either equal in number of stacks (if only the left vector stack number increases) or again $(t_1,\dots,t_{k+1}) \prec (u_1,\dots,u_{\ell+1} )$ where $k+1 \prec \ell +1$. I have two problems here. The first is that I can't prove this for case number 2 and also this proof is if we supposed $A^{i-1} \prec O^{i-1} $.

Denote the current state of the stacks as a $k$-vector $t=(t_1,\dots,t_k)$, where $k$ counts the number of stacks, $t_i$ is the number on the top of the $i$th stack, and I assume you have sorted the $t_i$ so that $t_1 < t_2 < \dots < t_k$.

Define a total order on state vectors as follows: $(t_1,\dots,t_k) \prec (u_1,\dots,u_\ell)$ if $k<\ell$, and $(t_1,\dots,t_k) \prec (t_1, \dots, t_j, u_{j+1}, \dots, u_k)$ if $t_{j+1} < u_{j+1}$.  Basically, this is comparing state vectors first by length (i.e., number of stacks), and comparing equal-length vectors by lexicographic order.

Now I suggest that you use the "greedy stays ahead" proof strategy, to try to prove by induction that if $A^i$ is the state of the stacks after $i$ steps of your algorithm and $O^i$ is the state after $i$ steps of the optimal algorithm, then $A^i \preceq O^i$.  I will let you work out the details of this proof to see whether you can prove it.  If you can do that, you will be done.  Letting $A$ be the final state after running your algorithm and $O$ the final state after running the optimal algorithm, it follows that $A \preceq O$.  Therefore, by the definition of $\prec$, $f(A) \le f(O)$.  This shows that your algorithm is as good as the optimal algorithm.

In other words, use "greedy stays ahead" to try to prove your algorithm correct, but you'll need to keep track of more information than just the number of stacks used so far; you need a more fine-grained measure of what it means to be "ahead" than just the number of stacks.


How does image reconstruction take place in neural network? I am reading through and thinking about how neural network works and have been reading about convolutional neural networks (CNN). I am particularly interested in image filtering (or enhancing) using CNN. The thing that confuses me is, how exactly does CNN produce the output, filtered/enhanced image? From what I understand each layer convolves the previous input into more distinctive features, so aren't we essentially losing details? How would the network then know that, for example, this noisy image A, should be cleaned up here and there as such trained to produce a clean image B?

A plain CNN normally isn't used to produce an image as output; but if you combine it with deconvolution layers, then you can produce an image as output.


Combining merge sort and insertion sort A cache-aware sorting algorithm sorts an array of size $ 2^{k} $  with each key of size 4 bytes. The size of the cache memory is 128 bytes and algorithm is the combinations of merge sort and insertion sort to exploit the locality of reference for the cache memory (i.e. will use insertion sort when problem size equals cache memory).

  What are the best case and worst case running time of the algorithm?

Basic Idea

For small values of n insertion sort runs faster than merge sort . Hence insertion sort can be used to Optimize merge sort

Basic idea is apply insertion sort on sublists obtained in merge sort and merge the sorted (using insertion sort) lists

Coming to Question
Base Condition
If each word is 4-byte long, then a 128-byte cache contains 32 words. Therefore, if the problem size is 32 or less, the instance will be immediately solved by Insertion Sort, otherwise it will be split in two sub-problems with the same size, which will then have to be merged
Time Complexity

Total Complexity = Complexity Insertion Sort + Complexity of Merge Sort

We have $n$ elements . We are dividing it to $\frac{n}{x}$ sublist each contain x elements each

Complexity Of Merge Sort

Total work done by merge sort in copying $n$ elements from each level to upper level is $O(n)$
Number of levels = number of sublists or small problem = $O(\log \frac{n}{x})$
Complexity of Merge sort : $O( n \log \frac{n}{x} )$

Complexity Of Insertion Sort

We are sorting $ \frac{n}{x} $ lists each of $x$ elements using insertion sort so complexity contributed by insertion sort is $\frac{n}{x} $ INSERTION ${x}$

Total Complexity =  $\Theta ( \frac{n}{x}  \ \text{INSERTION} \ (x)  +  n \log \frac{n}{x} )$

Best Case

is when Insertion sort perform in best case with $O(n)$ ie $\text{INSERTION} \ (x) = x$
Best Case Complexity=Total Complexity =  $\Theta ( n  +  n \log \frac{n}{x} )$

Worst Case

is when Insertion sort perform in best case with $O(n^{2})$ ie $\text{INSERTION} \ (x) = x^{2}$
Best Case Complexity=Total Complexity =  $\Theta ( nx  +  n \log \frac{n}{x} )$

More Information : Gate Overflow - Sorting Algorithm


Optimize binary search on Segment Tree by storing past result Goal
Let $A[n]$ be an arbitrary array of integers of length $n$. Let $S$ be a segment tree, represented by an array of records: each record containing the left and right bounds ($[l,r]$) of the segment the node covers, and a "sum" value equal to $\sum_{k=l}^rA_k$. I would like to perform a Weighted Random Selection on $A$, and because $S$ is a balanced binary tree, I can perform a binary search by traversing $S$ and do WRS in $\Theta(\lg n)$ time. In this case, the domain of my random variable $r$ is $[0,\sum_{k=1}^nA_k]$.
Now, suppose I delete the element $A_d,d\in[1,n]$, but because reconstructing $S$ takes $\mathcal{O}(n\lg n)$ time, I choose to let $S$ remain unmodified.
To perform WRS in this case, I am thinking that instead of starting from the first element of $A$, I can start from the $(d+1)$st element, tighten the domain of $r$ to $[0,(\sum_{k=1}^nA_k)-A_d]$ ($A$ here refers to the array before deletion, since the original values are stored in the "sum" values of the leaf nodes of $S$), and wrap back around to the start if I reach the end of $A$ while searching. The trouble is that the nice property of $\Theta(1)$ time needed at each iteration of the binary search (thanks to the balanced binary tree property of $S$) is no longer true. Now, each iteration of the binary search takes $\mathcal{O}(\lg n)$ time (summation over arbitrary segment in $S$), and since the binary search is $\Theta(\lg n)$, WRS done this way takes $\mathcal{O}(\lg^2 n)$ time.
Is it possible to perform WRS on $S$ in $\mathcal{O}(\lg n)$ time while omitting $A_d$?

Attempt at a solution
An easy way to make this operation faster is storing the cumulative sum calculated from the last iteration of binary search, and only calculate the ranged sum from the last midpoint to the current midpoint. This halves the size of the segment to be calculated at each iteration. However, this still appears to be in $\mathcal{O}(\lg^2 n)$ time. Halving the size of the segment at each iteration means $\lg(n)+\lg(\frac{n}{2})+\lg(\frac{n}{4})+...+1=\mathcal{O}(\lg \frac{n^{\lg(n)}}{2^{\lg(n)}})=\mathcal{O}(\lg^2 n)$ array accesses.

There turns out to be a very simple way to do this in $\mathcal{O}(\lg n)$:

Restrict the domain of $r$ to $[0,(\sum_{k=1}^nA_k)-A_d]$
If $r≥\sum_{k=1}^{d-1}A_k$, add $A_d$ to $r$.
Search using the original method.

Finding $\sum_{k=1}^{d-1}A_k$ is $\mathcal{O}(\lg n)$ time, finding $A_d$ from $S$ is $\Theta(\lg n)$ time, and the binary search is $\Theta(\lg n)$ time.


Remove from black/red tree subtree with red root, red sibling and black parent in $O(\lg n)$ How can i remove from a red/black tree a subtree whose root and its sibling are red, and their parent is black, in $O(\lg n)$ time, while keeping the red/black properties at the end of the process?

In other words:
I have a black/red tree with $n$ nodes, a given black node $y$, and his two red children $x$ and $z$. How can I delete the subtree of $x$ in $O(\lg n)$ time, while keeping the red/black tree properties at the end of the process?

This is an homework question.

The solution is to delete the sub-tree $x$ ($O(\lg n)$),
then replace sub-tree $z$ instead of sub-tree $y$ ($O(1)$),
then turn $z$ to black ($O(1)$),
and finally insert $y$ as usual ($O(\lg n)$).


Is my theorem about $P \neq NP$ correct? It is known that there are problems in P that, provably, are not
solvable in less than $O(N^k)$, for some $k$. Now consider some infinite
set $K \subseteq \mathbb{R}^+_0$ such as K is unbounded from above (you
can think of $K$ as being $\mathbb{N}$, for easy reasoning).

Theorem: If there exists at least one problem in P for each $k \in K$ that can't be solved in less than $O(N^k)$ steps, then $P \neq NP$.

Proof: Assume that $P = NP$, what implies that there is an algorithm that can solve some NP-complete problem in $O(N^q)$ steps, for some $q$. Since the problem is NP-complete, any NP problem can be reduced to it in $O(N^r)$ steps, for some $r$. Thus, every problem in $NP$ (so, also in $P$) can be solved in $O(N^r + N^q)$ steps. Since $K$ is unbounded from above, there are infinitely many $k \in K$ such as $O(N^k) > O(N^r + N^q)$, and so, for each of these $k$, there is at least one problem in P that can't be solved in $O(N^r + N^q)$ steps. But, since we assumed $P = NP$, every problem can be solved in $O(N^r + N^q)$. Contradiction!

So, to prove that $P \neq NP$, it suffices to find a class of
hard P problems, parameterized by a number $k$ -- lets call each of them
HARDP-$k$ -- that for each given $k$, it is proven that the best
algorithm that solves HARDP-$k$ has time complexity of $O(N^k)$.

If such a class is too hard to define, other less straight
strategies can be taken. For instance, without actually defining
HARDP-$k$, it suffices to prove that there exists infinitely many
problems in P with ever increasing time complexity for the best possible
algorithm that solves it.

So, my questions: 1) Is my theorem correct? 2) Is it already known? 3) Is it of any relevance?

I don't think the theorem is correct.  At least, your proof is not correct.  The problem is in the second sentences of your proof:

  Since the problem is NP-complete, any NP problem can be reduced to it in $O(N^r)$ steps, for some $r$.

This statement is not correct.  There's no guarantee there is a single $r$ that works for every NP problem.  You might have a different value of $r$ for each NP problem, with no upper bound on the set of all $r$.  (To give a silly example: Maybe for 3SAT $r=3$, for 4SAT $r=4$, for 5SAT $r=5$, and so on.  Don't take this example too seriously; it's just to give you the idea.)


Pumping lemma not regular How would about proving this is not regular with the pumping lemma. Please include all steps and explain all steps. I am really new with this.

$1^{2x}0^y$ and $y>= x$

Does it matter which side you pump? How do you pick which side to pump?

This is what I was thinking:

$$u = 1^{2x}$$
   $$v = 0^y$$
   $$w = 1^{2x}0^y$$

Am I on the right track? What else do I need to do?

assuming you have a pump length $p$ then there is a string $1^{2x}0^y$ with $p \lt x \le y$ as part part of the language

thus the partition $uvw$ with $\text{length}(uv)<p$ must have $uv$ as all $1$s

this means that your pump string $v$ contains all $1$ which if pumped can create twice as many $1$ than $0$s which is not part of the language. QED


What is the difference between Consensus and Leader Election problems? According to this paper written by Lamport, `selecting a unique leader is equivalent to solving the consensus problem'.

Based on the above quote, my question is: What is the difference between consensus and leader election problems?

My answer: I think that there is no theoretical difference between them. They are two terms with the same meaning, but they are used in different context. When the context is related to data stores, replication, or related subjects, 'consensus' is used, otherwise, 'leader election' is used.

Note: In the above paragraph, 'theoretical' means the way of defining a true consensus and leader election algorithm. A true consensus and leader election algorithm should satisfy three properties-- termination, agreement, and integrity.

This is not a matter of terminology: they're related, but different concepts.

A consensus algorithm is one that allows all the participants in a distributed system to choose a value from a set in such a way that all the participants choose the same value. A solution to the consensus problem is a distributed algorithm that has the following properties:

At the beginning, each participant $i$ has an initial value $v^0_i$.
At the end, all the participants must have the same value: $\forall i, \forall j, v_i = v_j$.
The common final value must be the initial value of at least one of the participants: $\exists i, v_i = v^0_i$.

A leader election algorithm is a special case of consensus algorithm where the set is the set of participants. The leader election problem consists of requiring a leader election whenever there is no leader. If there are failures, this may require running more than one election, because a new election becomes necessary when the current leader fails.

In the absence of failures, if you can solve consensus then you can solve the leader election problem: apply consensus with every participant initially choosing themselves. Conversely, if you can elect a leader, then you can solve consensus by having everybody choose the leader's value. This is often how consensus is solved in practice: choose a leader (using a specialized consensus algorithm), then the leader broadcasts its choice of value each time a consensus is needed.

However, if there are failures, this equivalence no longer holds. There are failure models where it's possible to solve consensus, but not to elect a leader. See Laura S. Sabely and Keith Marzullo, Election Vs. Consensus in Asynchronous Systems, Cornell University technical report, 1995. The gap is that certain failure detectors are sufficient to run a consensus algorithm, so they are sufficient to run a leader election, but they are not sufficient to solve the leader election problem, because they aren't sufficient to detect when a new leader election is needed.


Represent a 5 card poker hand A deck of cards is 52. A hand is 5 cards from the 52 (cannot have a duplicate).

What is the least amount of bits to represent a 5 card hand and how?
A hand is NOT order dependent (KQ = QK).  64329 = 96432

Yes, can use 52 bits. That can represent a hand of any number of cards.

Given a hand is exactly 5 cards is there a way to represent it with less than 52 bits.

A single card can be represented with 6 bits = 64.  So could just use 6 bits * 5 cards = 30 bits.  But that would be order dependent.  I could just sort and this should work. If that would not work please let me know.

Is there a way to get the key to 32 bits or under and not have to sort the 5 card tuple.

This is for poker simulations and sorting would be a lot of overhead compared to just generating the hand.  If I have a dictionary with the relative value of each hand it is two simple lookups and a comparison to compare the value of two hands. If I have to sort the hands first that is large compared to two lookups and a comparison.  In a simulation will compare millions.  I will not get sorted hands from the simulation.  The sort is not simple like 52 51 50 49 48 before  52 51 50 49 47.  You can have straight flush quads ....

There are 2598960 possible 5 card hands.  That is the number of rows.  The key is the 5 cards.  I would like to get a key that is 32 bits or under where the the cards do not need to be sorted first.

Cannot just order the list as many hands tie. Suit are spade, club, diamond, and heart.  7c 8c 2d 3d 4s = 7s 8s 2c 3c 4h.  There is a large number of ties.

The next step is 64 bits and will take the hit of the sort rather than double the size of the key.

I tested and SortedSet<int> quickSort = new SortedSet<int>() { i, j, k, m, n }; doubles the time of the operation but I still may do it.

It gets more complex. I need to be able to represent a boat as twos over fives (22255).  So sorting them breaks that. I know you are going to say but that is fast.  Yes it is fast and trivial but I need as fast as possible.

C# for the accepted answer:

private int[] DeckXOR = new int[] {0x00000001,0x00000002,0x00000004,0x00000008,0x00000010,0x00000020,0x00000040,
                                    0x00000080,0x00000100,0x00000200,0x00000400,0x00000800,0x00001000,0x00002000,
                                    0x00004000,0x00008000,0x00010000,0x00020000,0x00040000,0x00080000,0x00100000,
                                    0x00200000,0x00400000,0x00800000,0x01000000,0x02000000,0x04000000,0x07fe0000,
                                    0x07c1f000,0x0639cc00,0x01b5aa00,0x056b5600,0x04ed6900,0x039ad500,0x0717c280,
                                    0x049b9240,0x00dd0cc0,0x06c823c0,0x07a3ef20,0x002a72e0,0x01191f10,0x02c55870,
                                    0x007bbe88,0x05f1b668,0x07a23418,0x0569d998,0x032ade38,0x03cde534,0x060c076a,
                                    0x04878b06,0x069b3c05,0x054089a3};
public void PokerProB()
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    HashSet<int> cardsXOR = new HashSet<int>();
    int cardXOR;
    int counter = 0;
    for (int i = 51; i >= 4; i--)
    {
        for (int j = i - 1; j >= 3; j--)
        {
            for (int k = j - 1; k >= 2; k--)
            {
                for (int m = k - 1; m >= 1; m--)
                {
                    for (int n = m - 1; n >= 0; n--)
                    {
                        counter++;
                        cardXOR = DeckXOR[i] ^ DeckXOR[j] ^ DeckXOR[k] ^ DeckXOR[m] ^ DeckXOR[n];
                        if (!cardsXOR.Add(cardXOR))
                            Debug.WriteLine("problem");
                    }
                }
            }
        }
    }
    sw.Stop();
    Debug.WriteLine("Count {0} millisec {1} ", counter.ToString("N0"), sw.ElapsedMilliseconds.ToString("N0"));
    Debug.WriteLine("");
}

If we have a set of size $n$, you can represent an element of the set using $\lceil \lg n \rceil$ bits.  You say that there are 2598960 possible 5-card hands.  That means that a 5-card hand can be represented using just $\lceil \lg 2598960 \rceil = 22$ bits.  22 bits is significantly shorter than 30 bits.

How does the representation work?  There are various options, with different tradeoffs.  I list two below.

Hard-coded dictionary

In this case, the number of possible 5-card hands is small enough that you could just have a hard-coded dictionary that lists all 2598960 hands, and you represent a hand by its index in the dictionary (represented in binary).

In other words, the dictionary can be a sorted list of hands.  Each hand is the 5-tuple of the cards in the hand, in sorted order.  You can look up a hand in the dictionary using binary search and find its corresponding index; and given an index, you can find the correspond hand.  Or, you could store the dictionary as a hashmap that maps from the hand to its index.  The index is an integer between 0 and 2598959, so it can be represented using 23 bits.

This approach will work and be very simple to program, but it is wasteful in space (size of the program executable).

Ranking/unranking

Alternatively, if you care, there are better methods.  See, e.g., any of the following references:

https://en.wikipedia.org/wiki/Combinatorial_number_system
East Side, West Side.  Lecture notes, Herbert S. Wilf, August 14, 1999.  Sections 3.7-3.8.
https://computationalcombinatorics.wordpress.com/2012/09/10/ranking-and-unranking-of-combinations-and-permutations/
https://stackoverflow.com/q/3143142/781723

The general topic is known as "ranking (and unranking) of combinations".  These are a little more complex to implement and understand, but avoid the need to include a hard-coded dictionary in the program.


Rice's Theorem: implication of having an undecidable property I understand the assumptions that have to be true about a property or set of properties in a Turing machine description for Rice's Theorem to apply.

But then what?  If a set of Turing machines have an undecidable property, is the language itself necessarily undecidable? Or only if you can find a reduction from a known-undecidable machine is the language undecidable?

What does it really say about a language if it has an undecidable property? Are machines that recognize that language undecidable?

An undecidable property $\pi$ of Turing machines is the same as an undecidable language consisting of all encodings of Turing machines satisfying $\pi$. We identify the property with the language of encodings of Turing machines satisfying the property.

The fact that a language is undecidable just means that no Turing machine decides the language — this is the definition of undecidability. In particular, no machines recognize the language, assuming recognize means decide; a machine $T$ decides a language $L$ if $T$ terminates on all inputs, on inputs $x \in L$ returns $1$, and on inputs $x \notin L$ returns $0$. A machine cannot be undecidable, only a language can be undecidable.


Search algorithm to find integer input that produces the first 'True' (bool: 1) occurence of a computationally expensive boolean function A boolean-valued function defined in the set of positive integers, $\mathcal Z$.

$$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in \mathcal Z $$

$f(n)$ is computationally expensive and it's analytical form (a closed-form equation producing these binary-valued outputs is unknown, since it is the result of a time-domain simulation of complicated system of non-linear PDEs meeting certain exit conditions etc.). Furthermore, $\frac{\partial{f}}{\partial{n}}$ is also obviously not available.

The goal is to compute $n\ast$, i.e. the first occurrence of the integer-valued function input, $n$ that produces a Boolean $1$. Needless to say, this can be trivially achieved in computer code by using a simple $for$ loop and rejecting the values of $n$ one by one, until we hit $n\ast$.

The lower and upper bounds, $n_{min}$ and $n_{max}$ are known apriori.

However, given the expensive nature of computing $f(n)$, I am looking for an efficient algorithm beyond this naive implementation, especially one that requires small number of function evaluations. A pseudo-code implementation of your proposed solution would be much welcome too.

A conceptual schematic/visualisation of the problem is also shown here, purely to aid the understanding of the task at hand

Use binary search.

You know that the correct value is somewhere in the range $[n_\min,n_\max]$, so pick $t = \lfloor (n_\min+n_\max)/2 \rfloor$ (the point halfway in the middle), and evaluate $f(t)$.  This will either tell you that $n^*$ is in $[n_\min,t]$ or that $n^*$ is in $[t+1,n_\max]$.  Now you can repeat on the smaller interval.  Each time, the width of the interval decreases by a factor of two, so after $\lg (n_\max-n_\min)$ iterations, you will find the correct value of $n^*$.  This is much faster than trying all $n_\max-n_\min$ possible values of $n^*$.


Is it possible that $L=NP$? According to Wikipedia and other sources, the question whether $L=P$ is an open problem, and of course everyone is familiar with the problem of whether $P=NP$. However, I found absolutely no information online regarding a possible equality between $L$ and $NP$.

Such an equality doesn't directly violate the space-hierarchy theorem or the time-hierarchy theorem, and so I don't have any idea how to disprove it.

The question whether $L = NP$ is an open problem [1], so yes, it is possible.  However, it is considered unlikely, or in other words, most believe that $L \subsetneq P \subsetneq NP \subsetneq PSPACE$, but we only know that $L \subsetneq PSPACE$ [2, 3].

References:

[1] Taking Passes at NP Versus L — Gödel's Lost Letter and P=NP
[2] L/P/PSpace vs P/NP — cstheory.stackexchange.com
[3] If P=NP, then is L=NL? — cs.stackexchange.com


Why does going from 2's complement (in binary) to the positive value by completing to 1 then adding 1 work? I'm studying Computer science and this has confused me for a long time since our professor didn't give any proof.

When changing from 2's complement to the positive value, we can go in reverse (by subtracting 1, then using 1's complement), and that's clear why it works.

But our professor told us another method which is taking the number, using 1's complement, THEN adding 1.

I don't understand why the second method works.

Suppose that your integers are $n$ bit long. One's complement changes $x$ to $2^n-1-x$, since adding $x$ to its one's complement gives $\underbrace{1\dots 1}_{n}{}_2 = 2^n-1$.

Subtracting 1 and taking one's complement changes $x$ to $2^n-1-(x-1) = 2^n-x$.

Taking one's complement and adding 1 changes $x$ to $(2^n-1-x)+1 = 2^n-x$.


Why is the lower bound for sorting strings Ω(d + nlogn)? I'm taking an Advanced Algorithms course. I'm currently studying efficient algorithms for sorting strings. In this chapter, it is provided a lower bound for the time complexity of $\Omega(d + n\log{n})$, where d is the sum of the distinguishing prefixes of all the strings in our set S and n is the cardinality of the strings set S. The book says this is the minimum number of comparisons any algorithm must take, and I cannot figure out why. Can you help me? Thank you.

The time complexity you indicated is the lower bound of your specific problem. A lower bound is the worst-case running time of the most optimized TM that recognizes membership in the language.

Lover bound for sorting algorithms is $\Omega(n \log n)$ this means that it is not possible to do better than this and all the sorting cases (instances) may have a temporal complexity $t \geqslant\Omega(n \log n) $.

For a simple proof of the former lower bound you can take a look at this.


Can a tree be traversed without recursion, stack, or queue, and just a handful of pointers? Half a decade ago I was sitting in a data structures class where the professor offered extra credit if anyone could traverse a tree without using recursion, a stack, queue, etc. (or any other similar data structures) and just a few pointers.  I came up with what I thought was an obvious answer to that question which was ultimately accepted by the professor.  I was sitting in a discrete math class with another professor in the same department--and he asserted that it was impossible to traverse a tree without recursion, a stack, queue, etc., and that my solution was invalid.

So, is it possible, or impossible?  Why or why not?

Edit:  To add some clarification, I implemented this on a binary tree which had three elements-- the data stored at each node and pointers to two children.  My solution could be extended to n-ary trees with only a few changes.

My data structures teacher did not put any constraints against mutating the tree, and indeed I found out later that his own solution was to use the child pointers to point back up the tree on his way down.  My discrete math professor said any mutation of a tree means that it is no longer a tree according to the mathematical definition of a tree, his definition would also preclude any pointers to parents--which would match the case where I solved it above.

A lot of research in this area has been done, motivated by method of "cheaply" traversing trees and general list structures in the context of garbage collection.
A threaded binary tree is an adapted representation of binary trees where some nil-pointers are used to link to successor nodes in the tree. This extra information can be used to traverse a tree without stack. However, an extra bit per node is necessary to distinguish threads from child-pointers.
Wikipedia:Tree_traversal
As far as I know binary trees implemented using pointers in the usual fashion (left and right pointer per node) can be traversed using the method of threads, in a method attributed to Morris. The NIL-pointers are temporarily re-used to thread a path back to the root. The clever part is that during traversal one can distinguish the original edges from the temporary thread-links, using the way they form cycles in the tree).
Good part: no extra data structure. Bad part: slightly cheating, the stack is inside the tree in a clever way. Very clever.
A proof of the hidden stack is shown in P. Mateti and R. Manghirmalani: Morris's Tree Traversal Algorithm Reconsidered DOI:10.1016/0167-6423(88)90063-9
J.M. Morris: Traversing binary trees simply and cheaply. IPL 9 (1979) 197-200 DOI:10.1016/0020-0190(79)90068-1
Then there also is Lindstrom scanning. This method "rotates" the three pointers involved in each node (parent and two children). If you want to perform any decent pre-order or post-order algorithms you need extra bits per node. If you just want to visit all the nodes (three times, but you never know which visit you perform) then it can be done without the bits.
G. Lindstrom: Scanning list structures without stacks or tag bits. IPL 2 (1973) 47-51. DOI:10.1016/0020-0190(73)90012-4
Perhaps the most straightforward way is a method by Robson. Here the stack needed for the classic algorithm is threaded through the leaves.
J.M. Robson: An improved algorithm for traversing binary trees without auxiliary stack IPL 1 (1973) 149-152. 10.1016/0020-0190(73)90018-5
IPL = Information Processing Letters


Language to Construct Finite State Transducer I am attempting to write a Finite State Transducer module in OCaml, because I think it's a good exercise, which is because I have been teaching myself Natural Language Processing.

You typically construct finite automata using regular expressions, for example (a | b).

What language does one typically use to construct Finite State Transducers?

You can't use Regular Expressions alone, because that defines only the input string, but I need some method to map corresponding output symbol.  I have thought about having something like this ((a,x) | (b, y)), where the tuple (a,x) is composed of the component a input value, and the component x is the corresponding output value.  Would that work in general for constructing FST?

Yes, such a specification would work. Basically a FST is a finite state automaton, with different labels on the edges. We can go from FST to regex by a standard algorithm. The same method works with transducers, only the labels are now pairs of strings. The concatenation of labels is done component-wise: $(a,x)(b,y) = (ab,xy)$.

There are several types of FST. To obtain a general one both input and output component are strings, not just letters. It is not difficult to see that alternatively one might require that both input and output are either a letter or the empty string.

All said, I personally prefer as a "language" the finite state graphs: they are easy to "program".


Find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$ I want to find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$

I've tried the following:

$G=(V,\Sigma,R,S)$ with $\Sigma=\{a,b,c,\lambda\}$, $V=\{S,B\}$, $S=S$ and $$R=\{S\to \lambda\mid aSc\mid B,\;B\to bBc\mid \lambda\},$$
which would output $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$, in my opinion. I've tried to test my grammar by applying the rules in different combinations and I didn't spot any error yet.

So I'm asking myself:
Is there a way to to see if $L(G)=L$ or do I need to assume, that I've done everything correctly after testing some cases?

$S\to\lambda$ is unnecessary because $S\to B$ and $B\to\lambda$.
The grammar recognizes the desired language.

You can prove the second assertion pretty easily using induction (for example on the length of the derivation, or the length of the sentence).

You'll probably find it easier to prove two assertions independently:

If a sentence is in $L$, then it is in $L(G)$.
If a sentence is in $L(G)$, then it is in $L$.

Together, these prove equivalence.


Term for an A*-like pathfinding strategy where only the heuristic goal distance matters I am trying to find a proper term for the A*-like best-first pathfinding strategy where the node to expand next is the one with the least estimated distance from the goal, regardless of its distance from the source.

In best-first search algorithms, the node to expand next is the most promising one according to some evaluation function (which may take into account the current global knowledge).  In the normal A* algorithm, the evaluation function is the sum of the length of the currently know shortest path from the source and the heuristic estimate of the distance to the goal.  Is there a standard term for a similar strategy where the evaluation function is just the heuristic distance to the goal?

I was thinking about greedy and hill-climbing, but greedy in this context seems to be just a synonym of best-first, and in what is commonly referred to as hill-climbing, there seems to be either no backtracking, or just one-step backtracking, that is, old unexpanded nodes are discarded at each step.


How a reduction can help up solve a problem? I am studying the basics of Computation Theory and I came up with an example I can't understand.

Let's have a language $L = \{\langle M\rangle \mid L(M) = \Sigma^{\ast} \}$, so $L$ contains codes of all Turing machines which generate all the words from $\Sigma^{\ast}$. It's been said that we can reduce $H$ (the halting problem) to $L$, so $H \leq_m L$. A mapping $f(\langle M, x\rangle) = \langle N\rangle$ was defined, where $N$ is a Turing machine coded as shown below:

N(y):
    if (M(x) accepts):
        accept
    reject

Now my problem is: I thought that if  $H \leq_m L$ then if we could solve $L$, we would be able to solve $H$ as well. By this I supposed that if we have a TM deciding on language $L$, we would be able to build a TM deciding on language $H$. But as for me, the machine above does not help me solve $H$ at all. It acually looks like if we could solve $H$, then we could solve $L$, but I can only see the machine above generate $\Sigma^{\ast}$, but not decide on it.

If any of my intuition is correct, a Turing machine $M_L$ deciding on $L$ would work like: take the code of another Turing machine $M_A$ and accept if $M_A$ generates all words from $\Sigma^{\ast}$ or reject when $M_A$ does not generate all words from $\Sigma^{\ast}$. How would this machine help me build a Turing machine deciding on the Halting problem?

This is a natural trap that almost everyone falls into when encountering this style of reduction for the first time - you have your logic inverted, but in an understandable way.

To start with, note a couple of things:

If $N$ accepts at least one string, it accepts every string, so $L(N)$ is either $\emptyset$ or $\Sigma^{\ast}$, nothing in between.
$\langle N \rangle$ is an encoding of a Turing Machine, and what we want to know is whether we can decide if $\langle N \rangle$ is in $L$ or not.

So the argument is by contradiction. Imagine that we did have a TM $X$ that decided $L$, then we could give it $\langle N \rangle$ and, as it decides $L$, it would say, correctly, $\mathrm{Yes}$ or $\mathrm{No}$.

But if it says $\mathrm{Yes}$, then we know that $M$ halts on $x$, because that's how we built $N$, and similarly if it answers $\mathrm{No}$, $M$ doesn't halt on $x$.

So having $X$ (i.e. being able to decide $L$) allows us to decide the Halting Problem, and hence we have a contradiction.

Note that we're not trying to 'run' $N$, we're asking if there can possibly be an $X$ that looks at $\langle N\rangle$ and says something about it (for every $N$).


Finding a pair of edge disjoint paths in a graph, such that the weight of each of them is bounded Given an undirected graph $G=(V,E)$, two distinct vertices $s,t\in V$, a weight function $f:E \to \mathbb{N}$, and a constant $M\in \mathbb{N}$, does there exist a pair of edge disjoint paths connecting $s$ and $t$, each of which has weight at most $M$?  In other words, we are given an upper bound on the path weights, and we want to know whether there exists two paths from $s$ to $t$ that don't have any edge in common.

Call this problem DPBP (for disjoint pair of bounded paths).

Is DPBP NP-complete?

A variant of this problem can be solved in polynomial time.  In particular, Suurballe's algorithm can be used to find a pair of edge-disjoint paths where the sum of their weights is minimal; thus, it can be used to decide whether there exists a pair of edge-disjoint paths such that their weights sum to at most $M$.  But what about when we require each path to have weight at most $M$, instead of requiring that their two weights sum to at most $M$?

DPBP is NP-complete.

I give a reduction from the partition problem. Define $\text{PART}=\left\{ {x_1,x_2,\ldots,x_n\in \mathbb{N}|\exists I:\sum_{i\in I}x_i=\sum_{i\not\in I}x_i} \right \}$.

Given an instance $\left \{ {x_1,\ldots ,x_n} \right \}$ of PART, we build a graph in the following way. For each $i\in \left \{{1,\ldots,n} \right \}$, we have a diamond like component. These components are connected in a row, starting from $s$ and ending at $t$:

The weight of the upper left edge in the $i\text{'th}$ component is $x_i$ and all other edges have weights $0$. The constant bounding the paths weight is $M=\frac{1}{2}\sum_{i=1}^n{x_i}$.

A path in this graph between $s$ and $t$ travels through all components. In order for two edge disjoint paths to fit in, each path should travel threw all components, taking either the upper or lower part of each.

Given a partition $I={i_1,\ldots ,i_k}\subset \left\{ {1,\ldots,n} \right\}$, let the first path go threw the upper parts of the components with indexes in $I$, and threw the lower parts of the other components. Since traveling threw the upper part of the $i$'th component costs $x_i$, the weight of this path is exactly $\sum_{i\in I}x_i$. In case the given partition is proper, this sum is exactly $\frac{1}{2}\sum_{i=1}^n x_i = M$.

The second path will be the complement path, i.e., it will go threw the lower part of each component with an index in $I$, and threw the upper part of each component with an index not in $I$. Therefore, its weight will be $\sum_{i\not \in I}x_i=\sum_{i=1}^n x_i - \sum_{i\in I}x_i=M$ as well.

Thus, the two paths are edge disjoint and bounded by $M$ as required.

Now, assume that we are given a pair of edge disjoint paths between $s$ and $t$, so that the weights of each is at most $M$. By the construction, the weight of each is exactly $M$. Let $I=\left\{ {i_1,\ldots,i_k} \right\}$ be the components with an upper part traveled by the first path. Obviously, $I$ partitions the $x_i$'s properly.


Calculating speedup for a two-way superscalar cpu I've been coming across a problem in one of my assignments requiring the calculation of the speedup of a two-way superscalar cpu. The problem is as follows:

There is a two-way superscalar CPU with 2 pipelines U & V. The instruction pipeline U processes the complex instructions, while the instruction pipeline V processes the simple instructions. The ratio of the processing times in the phases of pipelines U and V is 3:1. I'm required to calculate the processing time for 1000 instructions in GPSS (General Purpose Simulation System) - Student Version, for the following cases:

50% complex and 50% simple instructions
25% complex and 75% simple instructions
75% complex and 25% simple instructions
Probability of 50% complex and 50% simple instructions
Probability of 25% complex and 75% simple instructions
Probability of 75% complex and 25% simple instructions

I have the simulation files and i can deduce the execution time for each case T(Supuperscalar).

However I'm stuck with the requirement of finding the speedup for each case.

I'm aware that the speed up can be calculated as Speedup = T(Sequential)/T(superscalar) = k*n/k+(n-1) where k is the number of stages and n is instruction number, however I'm having a hard time figuring out how to calculate the sequential time for the above cases.

I would really appreciate if somebody can give me a hint here.

The speedup is the ratio of the time when using your superscalar CPU, divided by the time if you used a simple sequential CPU.  For the sequential CPU, imagine that at each step you can execute either pipeline U or pipeline V, but not both at the same time.  Simulate the workload on that kind of sequential CPU, and see what the execution time would be.


Is Lambda Calculus purely syntactic? I've been reading for a few weeks about the Lambda Calculus, but I have not yet seen anything that is materially distinct from existing mathematical functions, and I want to know whether it is just a matter of notation, or whether there are any new properties or rules created by the lambda calculus axioms that don't apply to every mathematical function. So, for example, I've read that:

"There can be anonymous functions":
Lambda functions aren't anonymous, they're just all called lambda. It is permissible in mathematical notation to use the same variable for different functions if the name is not important. For example, the two functions in a Galois Connection are often both called *.

"Functions can accept functions as inputs":
Not new you can do this in with ordinary functions.

"Functions are black boxes":
Just inputs and outputs are also valid descriptions of mathematical functions...

This may seem like a discussion or opinionated question but I believe that there should be a "correct" answer to this question. I want to know whether lambda calculus is just a notational, or syntactic convention for working with mathematical functions, or whether there are any substantial or semantic differences between lambdas and ordinary functions.

Ironically, the title is on point but not in the way you seem to mean it which is "is the lambda calculus just a notational convention" which is not accurate.

Lambda terms are not functions1. They are pieces of syntax, i.e. collections of symbols on a page. We have rules for manipulating these collections of symbols, most significantly beta reduction. You can have multiple distinct lambda terms that correspond to the same function.2

I'll address your points directly.

First, lambda is not a name that is being reused. Not only would that be extremely confusing, but we don't write $\lambda(x)$ (or $(\lambda\ x)$) which is what we'd do if $\lambda$ was a name for a function, just like we write $f(x)$. In $f(x)$ we could replace $f$ (if it were defined by a lambda term) with the lambda term producing something like $(\lambda y.y)(x)$ meaning $(\lambda y.y)$ is an expression that can represent a function, not a declaration declaring a function (named $\lambda$ or anything else). At any rate, when we overload terminology/notation, it is (one hopes) done in a manner where it can be disambiguated via context, that certainly can't be the case for lambda terms.

Your next point is fine but somewhat irrelevant. This is not a competition where there's Team Lambda Terms and Team Functions, and only one can win. A major application of lambda terms is studying and understanding certain kinds of functions. A polynomial is not a function though we often sloppily identify them. Studying polynomials doesn't mean one thinks that all functions should be polynomials, nor is it the case that polynomials have to "do" something "new" to be worth studying.

Set theoretic functions are not black boxes, though they are entirely defined by their input-output relation. (They literally are their input-output relation.) Lambda terms are also not black boxes and they are not defined by their input-output relation. As I've mentioned before, you can have distinct lambda terms that produce the same input-output relation. This also underscores the fact that lambda terms can't be functions, though they can induce functions.2

In fact, the analogy between polynomials and lambda terms is very close, and I suspect you may not appreciate the distinction between a polynomial and the function it represents, so I'll elaborate a bit.3 Typically when polynomials are introduced, usually with real coefficients, they are treated as real functions of a particular type. Now consider the theory of linear-feedback shift registers (LFSRs). It is largely the theory of (uni-variate) polynomials over $\mathbb F_2$, but if we think of that as a function $\mathbb F_2\to\mathbb F_2$, then there are at most $4$ such functions. There are, however, an infinite number of polynomials over $\mathbb F_2$.4 One way to see this is that we can interpret these polynomials as something other than $\mathbb F_2\to\mathbb F_2$ functions, indeed any $\mathbb F_2$-algebra will do. For LFSRs, we commonly interpret the polynomials as operations on bitstreams, which, if we wanted could be represented as functions $\mathbf{2}^{\mathbb N}\to\mathbf{2}^{\mathbb N}$, though the vast majority of such functions would not be in the image of the interpretation of an LFSR.

This applies to lambda terms as well, we can interpret both of them as things other than functions. They are also both much more tractable objects to work with than the typically uncountably infinite sets of functions. They are both much more computational than arbitrary functions. I can write a program to manipulate polynomials (with coefficients that are computably representable at least) and lambda terms. Indeed, untyped lambda terms are one of the original models of computable functions. This more symbolic/syntactic, calculational/computational perspective is usually more emphasized, especially for the untyped lambda calculus, than the more semantic interpretations of the lambda calculus. Typed lambda terms are far more manageable things and can usually (but not always) easily be interpreted as set theoretic functions, but can also usually be interpreted into an even broader class of things besides functions than the untyped lambda calculus. They also have a rich syntactic theory of their own and a very deep connection to logic.

1 It's possible the issue might go the other way. Maybe you have a misapprehension about what a function is.

2 This is actually not so straightforward. For the untyped lambda calculus, it doesn't really make sense to naively interpret arbitrary lambda terms as set-theoretic functions. You can start to see this when you try to articulate what the domain of the interpretation should be. If I interpret a lambda term as an element of a set $D$, I also want to be able to interpret it as a function on $D$ and into $D$ since I want to interpret application as function application. You end up with $D^D\subseteq D$ (or a weakening of this) which is true only of the singleton set. What we need for the untyped lambda calculus is a reflexive object, and for the category of sets there are no non-trivial reflexive objects. The story is quite a bit different for typed lambda terms, but can still be non-trivial.

3 If you are clear on this distinction, then the analogy should be pretty informative.

4 This issue doesn't occur with fields of characteristic 0, like the complex numbers, reals, rationals, or integers, so the distinction isn't as sharp, though it still exists.


Quantum state probabilities and amplitudes - absolute value squared? It has just appeared to me that I've overlooked a possibly important fact. When we want to calculate probability $p_x$ of measuring the state $X$ and we know the amplitude of $X$ is $\alpha$, we know that $p_x = |\alpha|^2$. Until today I thought that absolute value was not necessary anyway. However, it brings significant difference if we have complex amplitudes with non-zero imaginary parts.

For example, let's say we have a superposition of 16 states, where four amplitudes are like $\frac{i}{4}$, four like $\frac{-1}{4}$ and eight like $\frac{1}{4}$. If we keep with the recipe I wrote above, then this state is fine, as the sum of all probabilities is 1. However, if we skip the absolute value and compute probabilities like $\alpha^2$, then sum of all probabilities in the above state would be $\frac{1}{2}$ and the state would not be stable.

Is the recipe I wrote above ($p_x = |\alpha|^2$ for $\alpha$ being an amplitude of state $X$) correct? Do we calculate the absolute value of the amplitude before we square it?

Using $\alpha^2$ doesn't make sense since you get negative or even non-real probabilities! The correct "recipe" is indeed $|\alpha|^2$. This also meshes well with the fact that the operations you are allowed to apply are unitary.


Reducing 3-colouring to planar 3-colouring I was reading these lecture notes and I'm trying to understand how one would formally describe reducing 3-colouring to planar 3-colouring. The link pretty much describes the process but understanding the mathematical formalism is a bit over my head. In short, it seems that every edge crossing is replaced with some new graph. How does this work?

The idea is simple. Given an arbitrary graph embedded in the plane, what might make it non-planar is that edges could cross. By slightly perturbing the planar embedding (where we put the vertices), we can ensure that no more than two edges meet at a point.

The idea is to replace each crossing with a certain planar gadget $W$, which functions as a cloverleaf. The four vertices on the outside of the gadget consist of a horizontal pair $x_1,x_2$ and a vertical pair $v_1,v_2$. The gadget has the property that in any valid 3-coloring $c$, $c(x_1) = c(x_2)$ and $c(v_1) = c(v_2)$, and vice versa, for each choice of $c(x_1) = c(x_2)$ and $c(v_1) = c(v_2)$ there is such a coloring.

How do we use this gadget? Suppose that the graph has exactly one crossing, the edge $(a,b)$ crossing the edge $(r,s)$, we put a copy of the gadget with $x_1 = a$ and $v_1 = r$. The gadget ensures that $c(x_2) = c(a)$ and $c(v_2) = c(r)$, so if we connect $x_2$ to $b$ and $v_2$ to $s$, the new graph is 3-colorable iff the original one is (I encourage you to draw this, consulting the lecture notes). Plus, the crossing has been replaced by the gadget, which is itself planar.

The general case is more complicated but of the same spirit, and you can read about it in the proof. The idea is to replace each crossing with a copy of the gadget; two adjacent crossings on the same edge share vertices, as illustrated on page 124 of the lecture notes.

The difficult part in coming up with this reduction is constructing the gadget. The idea itself is pretty natural, and it is somewhat surprising that it can be made to work.


Why do we need increase_key procedure in max priority queue? Since if I want to increase the priority of a specific node, how do I find the node without linear searching it.

I need to pass the index to this function, which is in a way a bottleneck. So the question is, how can I avoid it? Or exactly this data structure doesn't provide any solution for this problem?

Link: web.cse.ohio-state.edu/~lai.1/2331/4.heapsort.pdf | Chapter 5: Priority Queues

In some algorithms, you'll be able to remember the index.

In others, you might need a separate data structure (e.g., a hash table) that maps from the node to its index.  When you insert a node into the priority queue, you also add it to that mapping.  When you need to know a node's index (e.g.,to call increase_key), you look it up in that mapping.


Complexity of two cycles which differ by $1$ in length Given an undirected graph $G(V,E)$, our problem asks whether $G$ contains $2$ simple cycles which differ by $1$ in length.

What is the complexity of this problem?

It belongs to NP obviously, and is NP-complete by a reduction from the Hamilton cycle problem on bipartite graph.

Given a bipartite graph with $2n$ vertices, add an isolated simple cycle of length $2n+1$. Since there is no odd cycle in a bipartite graph, the new graph has two cycles which differ by 1 in length if and only if there is a Hamilton cycle in the bipartite graph.


Scheduling optimization problem in theta(n) I've been told it is possible to find a solution to this optimization problem in $\Theta(n)$ but I still don't know how I could do it. I did find easily a solution in $n\lg (n)$ though. I only need to have a VALID solution, not the optimal.

This is the problem :

Let say you have n tasks that have a start time and a max time. Each task takes 1 unit of time to complete.

So for example :

T1 = 2,3
T2 = 1,4
T3 = 4,5
T4 = 1,5
T5 = 3,4

This means that T1 CAN be started at time 2 and must be done by time 3. So a correct solution could be :

  T2, T1, T5, T3, T4

Any idea on how I could create an algorithm in $\Theta(n)$? For now I thought of using a sorting algorithm that does not use comparison but it only works with integer so I can't really get a reference to an object or something.

Since there are no dependencies between tasks, you might try a greedy algorithm: at each step, take the task that has the smallest start time (of all remaining tasks), then move on to the next time step.  This does end up requiring you to sort.

If the start and end times are all bounded above by some constant times $n$, you might want to read up on non-comparison based sorting routines, such as counting sort.  These sorting algorithms can achieve $O(n)$ time (under those conditions), yielding a $O(n)$ time solution to your problem (under the condition that the start and end times are all bounded above by some constant times $n$).

If you have no guarantees on the range of possible start and end times, then as David Richerby explains in his comment, there is no hope of achieving $O(n)$ time: there is a reduction from sorting, as he explains, so $O(n \lg n)$ is about the best you can hope for if we have no guarantees about the start and end times.  That still might be plenty efficient in practice; for realistic values of $n$, $\lg n$ will be quite small, and standard sorting algorithms are extremely efficient.


NP-completeness of a Generalized Version of Subset Sum I am curious about the NP-completeness (or if not, an efficient algorithm) for the following generalization of the subset sum problem:
In subset sum, we are given a number $t$ and a collection $S$ of integers with $|S|=n$, and ask if we can use a subset $S'\subseteq S$ to sum up to $t$. We can generalize the problem by extending the operation allowed: instead with only addition, we can permit addition together with multiplication and parenthesization.
It seems with the extended case, the usual reduction technique of encoding 3SAT in the problem breaks down, as parenthesization together with multiplication is difficult to handle (on the other hand, it seems like multiplication itself is easier to handle, as it can be expressed as a summation of identical elements).
Intuitively this generalized problem looks much harder; however, I haven't managed to find a way to prove its NP-completeness. I'm wondering if it can be indeed proven to be NP-complete, and what sort of reduction technique could be used in this problem.

Without loss of generality consider an instance $\langle S, t \rangle$ of subset sum where $S$ contains only positive integers and $t \ge 1$ (zeros can be dropped from $S$, and the case $t=0$ is trivial).
Now build a new instance $\langle T, t' \rangle$  of your generalized version of subset sum by choosing $T = \{ (t+1)x : x \in S \}$ and $t'=t(t+1)$.
If the elements of a subset $S' \subseteq S$ sum to $t$, then the elements of $\{ (t+1)x : x \in S' \} \subseteq T$ sum to $\sum_{x \in S'} (t+1)x = (t+1)\sum_{x \in S'} x =(t+1)t = t'$.
If there is a subset $T' \subseteq T$ of elements that can be arranged in an expression $E$ (that uses only addition, multiplication, and parentheses) that evaluates to $t'$, then $E$ uses no multiplication.
Indeed, if $E$ used at least one multiplication, it would evaluate to at least $(t+1)^2 > (t+1)t = t'$ since each of the involved factors must be at least $(t+1)$.
As a consequence it must be that $t' = t(t+1) = \sum_{x \in T'} x$.
Let $S' = \{ \frac{x}{t+1} : x \in T' \} \subseteq S$. We have that $\sum_{x \in S'} x = \sum_{x \in T'} \frac{x}{t+1} = \frac{1}{t+1} \sum_{x \in T'} x = \frac{t'}{t+1} = t.$
This shows that your version of generalized subset sum is NP-complete (membership in NP is trivial).


Number of descendants of each node in a DAG 1) Is there a better algorithm than the naive O(|E|.|V|) to compute the number of descendants of each vertex in a DAG?

2) Is there an online algorithm to do so, assuming that nodes are added one by one and connect to a non empty subset of the existing nodes?

Context: I'm interested in the case where m = O(n), millions of vertices, tens of millions of edges typically.
Alternatively, counting the number of descendants which are also sinks would be useful.

A probabilistic approach would be min-hashing, as a way to represent the set of descendants of every node. The union of the min-hash structure is trivial, and the cardinality of the union can be estimated from the number of coincidences in the min-hashes.

However, I'm not sure how well behaved that would be when propagating up the DAG, intuitively it looks like errors would compound pretty fast.

Very related: https://cstheory.stackexchange.com/questions/553/what-bounds-can-be-put-on-counting-reachable-nodes-in-a-dag
And actually a duplicate of: https://cstheory.stackexchange.com/questions/18787/what-is-the-fastest-deterministic-algorithm-for-incremental-dag-reachability

Topologically sort the nodes in your DAG.
For each node N, set N.QueryCount = 0.
For each node N, in reverse topological order:

Set N.Descendants = {N} U {C.Descendants | C in N.Children}.
Yield (N, N.Descendants.Count) from the algorithm.
If N.Parents is empty, you can dispose of N.Descendants.
For each C in N.Children, increment C.QueryCount. If C.QueryCount == C.Parents.Count, you can dispose of C.Descendants.

This of course is expensive if your node degrees are large. Worst case complexity may not be significantly better than your unspecified "naive algorithm."

The issue is that this is a very difficult problem to solve.  Suppose there is a DAG with millions of nodes, millions of edges, etc. I show you this portion of the graph:

A--> B
 \-> C

How many descendants does A have?  The number of descendants of B plus the number of descendants of C minus the number of common descendants of B and C.  It's the third term that creates the difficulty.  You can't know just the number of descendants of B and C - you need to also know what the descendants are.


Construct NPDA for the language $L=\{w \mid w \in \{a,b\}^*$, $\text{the number of a's is at least the number of b's} \}$

I'm stuck trying to build an NPDA that accepts $L$.

You need to design a NPDA that behaves as follows:

If it reads "a" and stack is empty push "a" onto stack
If it reads "b" and stack is empty push "b" onto stack
If it reads "a" and top entry on stack is "a" the push "a" onto stack
If it reads "b" and top entry on stack is "a" the pop "a" from the stack
If it reads "a" and top entry on stack is "b" the pop "b" from the stack
If it reads "b" and top entry on stack is "b" the push "b" onto stack

The top entry on the stack is therefore "a" if the NPDA has read more "a"s than "b"s, and is "b" if it has read more "b"s than "a"s. If the stack is empty then the NPDA has read equal numbers of "a"s and "b"s.

The accepting states are therefore if the top entry of the stack is "a" or the stack is empty.


Ski design usaco problem alternative solution problem statement for SKICOURSE is this

Farmer John has N hills on his farm (1 <= N <= 1,000), each with an integer elevation in the range 0 .. 100. In the winter, since there is abundant snow on these hills, FJ routinely operates a ski training camp.

Unfortunately, FJ has just found out about a new tax that will be assessed next year on farms used as ski training camps. Upon careful reading of the law, however, he discovers that the official definition of a ski camp requires the difference between the highest and lowest hill on his property
to be strictly larger than 17. Therefore, if he shortens his tallest hills and adds mass to increase the height of his shorter hills, FJ can avoid paying the tax as long as the new difference between the highest and lowest hill is at most 17.

If it costs x^2 units of money to change the height of a hill by x units, what is the minimum amount of money FJ will need to pay? FJ can change the height of a hill only once, so the total cost for each hill is the square of the difference between its original and final height. FJ is only willing to change the height of each hill by an integer amount.

and Naive way of doing this problem is like this

The problem can be solved with different approaches. A simple idea is of course brute-force -- try all possible elevations and find the minimum amount. We can try all possible values as follows: try the modification for elevation interval (0,17) then (1,18), (2,19), ..., (83,100). For each elevation interval (i,i+17), we need to calculate the cost for each hill j:

If the elevation of hill j, say hill[j], is in the interval (i,i+17) then there is no cost.
If it is less than i then the cost increases by (i-hill[j])^2
If it is greater than i+17 then the cost increases by (hill[j]-(i+17))^2

Is there any better way of doing this i mean if limits exceed drastically

I know, this question is really old, but I will answer it anyway. You can just pick wether you higher the lowest distance or lower the highest one. Then greedy pick the cheaper one until you have your maximum height equal or smaller than 13. In this case, you only need O(max-min-13) steps.  Hope it helps.

Just keep in mind that you need to track the former changes because of the quadratic equation.


How does the length of the output of a problem inform its complexity? Consider the decision problem: Subset sum. For an input set of integers, it asks for a Yes/No answer to the question of whether or not we can find a subset of elements of this input that add up to 0. The output for this problem is $O(1)$ and simple (e.g. 1/0). This problem is NP-Complete, which as far as I understand is only defined for decision problems.

Now consider a problem associated with Subset sum that asks to output all such subsets that add up to 0.  As far as I understand, this is an optimization problem.

Moreover, the output of this problem could grow as $O(2^N)$ if $N$ is the size of the input array (i.e. the output grows as fast as the cardinality of the power set of the input).  If so, what does this say about the complexity or complexity class of this optimization problem?

More generally speaking, does the size of the output of an optimization problem provide a necessary lower bound on the complexity of the optimization or associated decision problems?

No, it's not an optimization problem.  It takes at least one step of computation per bit or word of output (depending on the model of computation), so since the output can be $\Omega(2^N)$, that means the worst-case running time will be $\Omega(2^N)$, no matter what algorithm you use.  Thus, the complexity is $\Omega(2^N)$.

Yes, the size of the output is a lower bound on the running time to produce that output.


What are the most used statements in programming (ranked)? I was wondering if there are any resources for a study/ranking of the most frequently used statements (by statements I mean assigning, invoking, instantiating etc, like in C#) in programming overall (or at least for one modern language).
This is for a private research project where I am writing my own bytecode assembler and compiler for a custom language.
For example, the C#-code:
int a = 0;
int b = a * 2;
DoSomething(a, b);

would have 2 assignments and 1 function call.
So I'm wondering is there any study or somethig similar, regarding the usage frequency of statement types in general?
thx in advance

I don't know about statement types, but there's been a lot of research over the decades about CPU instruction frequency and how it impacts ISA design, IR design, and VM design... but it's all for languages like C. See, for example, loads/stores/branch frequencies for the SPEC2017 benchmarks.
If your language is C-like, there are basically only two reasons to compile to a virtual machine:

The goal is portability and/or optimisation convenience, in which case it is an intermediate representation on the way to generating code for a real machine.
The goal is some unusual performance constraint, such as extremely fast compilation, or for the generated code to be as tiny as possible.

In managed/interpreted languages, the main considerations are:

If the VM code is also a distribution format (e.g. JVM or DotNET), size may be a factor.
When interpreting, maximising the amount of "actual computation" (as opposed to interpreter overhead) performed for each interpreted instruction.
When compiling (whether AoT or JIT), preserve as much of the relevant semantics of the source language as is needed for efficient optimisation, and discard (as far as possible) as much of the irrelevant semantics as possible.

Examples of that last point: Preserving basic types (integers, floats) is much more important than preserving non-basic types (structs, objects). Preserving the distinction between static calls and dynamic calls in OO languages is also extremely important.
I suspect that a reason why there isn't as much general research on object-oriented, managed, non-C-like languages (calling them "modern" is arguably misleading!) is because specific libraries and frameworks tend to dictate the style of programming that programmers do.
For C# specifically, if such information has been collected, it seems unlikely that Microsoft is telling anyone.


Why is the Turing Machine a popular model of computation? I am a CS undergraduate. I understand how Turing came up with his abstract machine (modeling a person doing a computation), but it seems to me to be an awkward, inelegant abstraction. Why do we consider a "tape", and a machine head writing symbols, changing state, shifting the tape back and forth?

What is the underlying significance? A DFA is elegant - it seems to capture precisely what is necessary to recognize the regular languages. But the Turing machine, to my novice judgement, is just a clunky abstract contraption.

After thinking about it, I think the most idealized model of computation would be to say that some physical system corresponding to the input string, after being set into motion, would reach a static equilibrium which, upon interpretation equivalent to the the one used to form the system from the original string, would correspond to the correct output string. This captures the notion of "automation", since the system would change deterministically based solely on the original state.

Edit:

After reading a few responses, I've realized that what confuses me about the Turing machine is that it does not seem minimal. Shouldn't the canonical model of computation obviously convey the essence of computability?

Also, in case it wasn't clear I know that DFAs are not complete models of computation.

Thank you for the replies.

Well, a DFA is just a Turing machine that's only allowed to move to the right and that must accept or reject as soon as it runs out of input characters. So I'm not sure one can really say that a DFA is natural but a Turing machine isn't.

Critique of the question aside, remember that Turing was working before computers existed. As such, he wasn't trying to codify what electronic computers do but, rather, computation in general. My parents have a dictionary from the 1930s that defines computer as "someone who computes" and this is basically where Turing was coming from: for him, at that time, computation was about slide rules, log tables, pencils and pieces of paper.  In that mind-set, rewriting symbols on a paper tape doesn't seem like a bad abstraction.

OK, fine, you're saying (I hope!) but we're not in the 1930s any more so why do we still use this? Here, I don't think there's any one specific reason. The advantage of Turing machines is that they're reasonably simple and we're decently good at proving things about them. Although formally specifying a Turing machine program to do some particular task is very tedious, once you've done it a few times, you have a reasonable intuition about what they can do and you don't need to write the formal specifications any more. The model is also easily extended to include other natural features, such as random access to the tape.  So they're a pretty useful model that we understand well and we also have a pretty good understanding of how they relate to actual computers.

One could use other models but one would then have to do a huge amount of translation between results for the new model and the vast body of existing work on what Turing machines can do. Nobody has come up with a replacement for Turing machines that have had big enough advantages to make that look like a good idea.


Why do we have free variables in mu-calculus? I'm reading the Model Chekcing book of E. M. Clarke and in the chapter about µ-calculus there is an example formula
$$
f = \mu Z. ((q \mathrel{\mathrm{AND}} Y) \mathrel{\mathrm{OR}} \langle a \rangle Z)
$$
As the author has mentioned, here $Y$ is a free variable, and we need an association list to pair $Y$ with the corresponding states. But why do we need it? Can it be replaced by an atomic proposition?

If you define the $\mu$-calculus to not allow free variables, you would have the problem that the components of a well-formed formula are not again well-formed formulas.

Consider a well-formed formula "$\mu Z . \varphi$", such that $Z$ occurs freely in $\varphi$ and $\varphi$ has no other free variables. If you were to exclude formulas with free variables from your definition, $\varphi$ would not be a well-formed formula.

This would make structural induction on formulas more complicated. For example the semantics of formulas (the set of states in which the formula holds) is usually defined inductively: You define the semantics of "$\mu Z . \varphi$" in terms of the semantics of $\varphi$. If your definition says $\varphi$ is not a well-formed formula, you would have to extended the induction to also cover these non-well-formed cases. If you have to consider these cases every time you do structural induction, you haven't really gained anything from excluding them in your definition.


Determining if my artificial neural network needs additional layers I have implemented a neural network for load forecasting in Microsoft Excel. My structure is very simplistic and involves only 1 hidden layer and 4 neurons. (See picture)

I trained my network with a very large set of data and the predictions are as decent as could be expected. However, when I go to try and predict the "future" using recent data, the network is only in the ball-park, not very close at all. Here is a plot of the actual numbers versus the forecast ones.

From looking at this chart, can it be determined if I need another layer or more neurons??

There isn't any hard and fast rule to determine that how much hidden layers would work. In your case, extra layer won't help that much, but extra features can (I'm pretty much sure). Weather forecasting, as far as I know, isn't something which can be determined using only 4 features (considering your input neurons). You can always come up with more and more features, which effectively help in predicting the weather. So, I'd suggest to look for more features (about 10 to 15 useful features), and come up with the following configuration of the network:
1.) Input: Number of neurons in he input layer should be equal to the number of features you calculate for each data entry.
2.) Output: If you can categorize the weather in, say, 5 different categories (sunny, rainy, foggy, stormy, meteor shower), then there can be 5 output neurons.
3.) Hidden: Number of neurons in the hidden layer is normally the mean value of the number of input, and output neurons. You can also have same number of neurons in the input, and hidden layer.