Transformation of a Product Buchi Game to a Parity Game Is there anyway to express a Product Buchi game as a parity game? There is no stochasticity in my original turn-based game and a Deterministic Buchi Automaton is constructed for LTL specifications.

I will assume that by "Product Buchi game", you mean the (synchronous) product of a deterministic Buchi automaton and some kind of plant or deterministic finite automaton that represents the rules of the game (so to speak) apart from the specification.

You then translated this product between the Buchi automaton and a deterministic automaton to a game by assigning atomic propositions (of which the actions of the two players are composed) or characters to the two players. You have a Buchi game then. Because in your question you state that you want to represent a Product Buchi game as a parity game, I will assume that you have this product Buchi game already.

Translating a Buchi game to a parity game is now easy: Let $\mathcal{F}$ be the set of accepting states/vertices/positions in the Buchi game. Then, you can replace $\mathcal{F}$ by the following coloring function (for every vertex $v$):

$$
c(v) = \begin{cases} 1 & \text{ if } v \in \mathcal{F} \\
0 & \text{ otherwise} \end{cases}
$$

This will give you a parity game in which the player who was formerly the Buchi player can ensure that the highest color visited infinitely often is odd if and only if it is able to win the Buchi game from which the parity game was translated.

If your definition of parity game reasons about the lowest color visited infinitely often, swap the 0 and 1 in the formula above. Likewise, add 1 to every number if the player should make sure that the highest/lowest color should be even. There are multiple definitions of parity game winning in the literature, which are however all equivalent.


Segmentation technique for handwritten text (cursive and unconstrained) Although I am new to the computer vision domain, I am tasked with automating handwritten text recognition from bank cheques. I first did some preprocessing(blurring and binarization) and then dilated it so that I could segment the words. But since the words are handwritten (cursive and unconstrained), the segmentation is failing most of the time. I read up on some research papers and it seems you can use neural networks for segmentation.Is that the correct approach? Are there other alternatives? Can someone shed some more light?

As mentioned in comments there is no one right way to recognize handwriting. That said, Here are two techniques you could explore.

Watershed segmentation works by creating a topological map of the image to determine which objects distinct and with or without connection to other objects. I recommend it to you because watershed excels at naturally or man-made round objects. It has been documented for use in handwriting recognition. This is an easy one to get started with too. You can simply call watershed in matlab, OpenCV, or scikit

Machine Learning / Deep Learning (ML) is a daunting term to some but we usually get the chance to stand on the shoulders of giants such that ML on images is about as difficult as editing an large collection of vacation photos. Bag of words is a particular technique which works well on finite object sets. Note that like most ML BoW requires pre-classified training materials so be prepared to provide at least 100 different samples of a cursive uppercase 'Q' along with all the other characters you wish to recognize. Nonetheless, if you've got the time and resources to train it, a ML solution can be incredibly powerful in handwriting recognition.


Is there a LL(K) Grammar which is not LALR(K) Grammar? It is easy to know that there are LALR(K) grammars which are not LL(K) because any grammar with left recursion which is LALR(K), is not LL(K) because all LL(K) grammar must be left recursion free. And the opposite? Is there a LL(K) Grammar which is not LALR(K) Grammar? Do you have an example?

Related:

Are regular expressions $LR(k)$?
https://stackoverflow.com/questions/14674912/why-are-there-lr0-parsers-but-not-ll0-parsers
https://stackoverflow.com/questions/36652221/relationship-between-lr0-ll0-lalr1-etc

Every $LL(k)$ grammar is $LR(k)$, but there are $LL(k)$ grammars which are not $LALR(k)$.

There's a simple example in Parsing Theory by Sippu&Soisalon-Soininen

$$\begin{align}S &\to a A a \mid b A b \mid a B b \mid b B a\\
A &\to c \\
B &\to c
\end{align}$$

The language of this grammar is finite, so it is obviously $LL(k)$. (In this case, $LL(3)$.) The grammar is also $LR(1)$. However, the grammar is not $LALR(k)$ for any value of $k$.

The canonical $LR(k)$ machine has two states with $LR(0)$ itemsets $\{[A\to c \cdot], [B\to c\cdot]\}$. These two states have different lookahead sets in each item, corresponding to the two different predecessor states before shifting $c$. The $LALR$ algorithm merges these two states, thereby losing the distinction between the lookahead sets. This produces two reduce-reduce conflicts. Since there is only one token of lookahead at this point, increasing $k$ would make no difference.


Algorithm to find repeated patterns in a large string For optimization purposes I'm trying to analyze a large list of executed program commands to find chunks of commands that are executed over and over again. This problem is similar to searching repeated substrings in a string. However, in my case I'm not looking for the longest substrings but rather smaller substrings that occur very often.

For example, say each command is represented by a letter, then a program might look like xabca yabca xabca yabca. If we are looking for the longest repeated substrings, the best result is xabca yabca. A "better" result would be abca, though. While being shorter, it occurs more often in the string. a occurs even more often on its own, but it would be considered a too short match. So an algorithm should be parameterizable by a minimum and maximum chunk length.

Things I have tried so far:

I played with suffix trees to find the longest repeated substrings that occur at least k times. While that is simple to implement, it doesn't work well in my use case, because also overlapping substrings are found. Trying to remove those wasn't very successful either. The approach mentioned in this post either gave wrong or incomplete results (or I misunderstood the approach), and it also doesn't seem to be customizable. Suffix trees still seem the most promissing approach to me. Perhaps someone has an idea how to include the minumim/maximum chunk lengths into the search here?

EDIT: I finally found a working algorithm for the longest non-overlapping repeated substring, explained here. My current implementation works fine for smaller inputs but has an excessive memory consumption for inputs larger than 10 MB (which shouldn't be a problem of the algorithm per se).
Another attempt was using the substring table that is created for the LZW compression algorithm. The problem with this approach is that is doesn't find repeated chunks that occur early and it also creates longer and longer table entries the farer it processes the input (which makes sense for compression but not in my use case).
My best solution so far is the brute-force approach, i.e. building a dictionary of every possible substring and counting how often it occurs in the input. However, this is slow for large inputs and has a huge memory consumption.
Another idea was searching for single commands that occur most frequently, and then somehow inspecting the local environments of those commands for repeated patterns. I didn't come up with a good algorithm here, though.

What else algorithms are there that could be useful in this scenario? What I'm looking for is not necessarily the best match but a good heuristics. My input data is pretty big, strings up to a length of about 100MB; the chunk sizes will usually be in the range from 10 to 50.

To improve your brute force, you would only need to look at the substrings of minimum length, as longer substrings will occur at most as many times as their own substrings. This should take linear time to create the dictionary, and O(nlog(n)) to sort.

If this is too memory intensive, you could do pruning by first brute-forcing this for say, substrings of length 2, and then only consider min-length substrings that contain at least k of the most common 2-length substrings for some threshold k.


Complexity of k-way merge with log n arrays of size n / log n I'm designing an in-place sorting algorithm to sort a collection of size $n$. Near the end of the sorting, it may end up with with $\log{n}$ sorted sub-sequences of size $\frac{n}{\log{n}}$. At this point, I use a very simple $k$-way merge algorithm that merges the sub-sequences pairwise until everything has been merged. This very case apparently represents the complexity bottleneck of the algorithm.

I'm repeatedly using the C++ function std::inplace_merge to perform the merging operations, which performs $Θ(N \log{N})$ comparisons most of the time, but may perform up to $O(N \log^2{N})$ comparisons if there isn't enough extra memory available, where $N$ corresponds to the sum of the sizes of the sequences to merge (in our case $2\frac{n}{\log{n}}$).

Taking all of that information into account, I can tell that repeatedly merging the sub-sequences pairwise until everything has been merged takes the following number of comparisons, step by step:

Step 1: $O(\frac{\log{n}}{2} * \frac{2n}{\log{n}} * \log^2{\frac{2n}{\log{n}}}) = O(n * \log^2{\frac{2n}{\log{n}}})$
Step 2: $O(\frac{\log{n}}{4} * \frac{4n}{\log{n}} * \log^2{\frac{4n}{\log{n}}}) = O(n * \log^2{\frac{4n}{\log{n}}})$
Step 3: $O(\frac{\log{n}}{8} * \frac{8n}{\log{n}} * \log^2{\frac{8n}{\log{n}}}) = O(n * \log^2{\frac{8n}{\log{n}}})$
$\ldots$

If I'm not mistaken, there will be $\log{k}$ steps where $k$ is number of sorted sub-sequences in the original collection, which is is $\log{n}$, hence there will be $\log{\log{n}}$ steps. This should yield an overall complexity along the lines of $O(\log{\log{n}} * n * \log^2{\frac{?n}{\log{n}}})$.

Now, to be perfectly honest, I've got no idea how to simplify this expression further, and since I'm describing a sorting algorithm, I would like to know whether it is more along the lines of $O(n \log{n})$ or $O(n \log^2{n})$.

Having computed the complexity of the other two steps of the algorithm, it appears that none of them performs more than $O(n \log{\frac{n}{\log{n}}})$ comparisons¹, which is intuitively smaller than $O(n \log{n})$, the lower bound for comparison sorting, so the k-way merge surely dominates the overall complexity and thus performs at least $O(n \log{n})$ comparisons.

Can you help me solve this complexity problem?

¹ Among the other steps, the bigger one is sorting $\log{n}$ sub-sequences of size $\frac{n}{\log{n}}$ with an $O(N \log{N})$ sorting algorithm, which has the complexity $O(\log{n} * \frac{n}{\log{n}} \log{\frac{n}{\log{n}}}) = O(n \log{\frac{n}{\log{n}}})$.

First of all, notice that whatever you were doing, the complexity up to this point can not possibly be $o(n \log n)$. If that were true, we could merge each sorted subsequence in time $O(n \log \log n)$, violating the well known bound of $\Omega(n \log n)$ for the worst case of a general sorting algorithm. In fact, $$\Theta\left(n \log \frac{n}{\log n} \right) = \Theta(n \log n - n \log \log n) = \Theta (n \log n)$$

Now, let's analyze the complexity of what you are proposing. In order to visualize all the merging that's going on, imagine inserting each sorted subsequence into a FIFO queue. At each step, we take the first two sequences of the queue, merge them, and put the result at the back of the queue. We take note of the sequence that is initially in front of the queue, and define a round as the set of all merging operations that happen between two subsequent appearances of the initial sequence at the front of the queue.

Observe that each round splits in half the queue size: let's say there are $r$ rounds, with $r \in \Theta(\log \log n)$. Let $\alpha = \frac{n}{\log n}$. Before the $h-$th round begins, the queue contains $\frac{n}{2^h \alpha}$ subsequences, each of which has length $2^h \alpha$. Therefore, the complexity of round $h$ is:

$$
\Theta\left( \frac{n}{2^{h+1} \alpha} \left( 2^{h+1} \alpha \log (2^{h+1} \alpha) \right) \right) = \Theta \left( n \log (2^{h+1} \alpha) \right)
$$

This yields an overall complexity of:

$$
\Theta\left( \sum_{h=0}^{r-1} n \log (2^{h+1} \alpha) \right) =
\Theta\left( nr \log \alpha + n\sum_{h=0}^{r-1} \log 2^{h+1} \right ) =
\Theta\left( nr \log \alpha + nr^2 \right )
$$

Now, remembering that:

$$
\Theta \left( \log \alpha \right) = \Theta \left( \log n - \log \log n \right) = \Theta(\log n)
$$

We conclude:

$$
\Theta\left( nr \log \alpha + nr^2 \right ) = \Theta(n \log n \log \log n)
$$


How do I determine if this argument is valid? I'm studying propositional logic the section on "valid arguments".

A self-assessment question reads

"Show whether or not the following argument is valid"

$\frac{P}{C}$

I don't know what function to apply to P to calculate C.

The solution in the back of the book shows the following truth table:

Variables   Premise Conclusion
P       C      P        C
F       F      F        F
F       T      F        T
T       F      T        F  <--
T       T      T        T

So the conclusion is that the argument is invalid because the premise is true and the conclusion false.

I understand that of course, but how do I calculate Conclusion? Do I just guess what it should be?

My teacher had the following to say:

  If P is True, C is True. If P is False, C is False.

  Swap it for 'Premise - I am thirsty' & 'Conclusion - I drink some water'

  The conclusion is dependant on the premises. If there is only one, they > will never differ and a Conclusion will never be False, with a True
  Premise.

This answer flies in the face of the answer in the book.

I pointed this out to my teacher and got the following:

  My understanding is that P is the only variable; C is the conclusion that represents what P might be i.e True or False, once evaluated.

So... in conclusion I find myself still confused

The argument $\frac{P}{C}$ means "If we assume that $P$ is true, we can prove that $C$ is true." For example, $\frac{A}{A\lor B}$ because, if you can prove that $A$ is true, then $A\lor B$ is also true: there's no way that $A$ can be true but $A\lor B$ can be false at the same time.

In the argument you've been give, $P$ and $C$ are completely unrelated. There is a way that $P$ can be true and $C$ can be false at the same time: specifically, $P=\mathrm{true}$, $C=\mathrm{false}$. Therefore, the argument is not valid.

You don't calculate the conclusion, per se. rather, you look for a situation in which the premise is true but the conclusion is false. If you can find such a pair of premise and conclusion, the argument is invalid. Conversely, if you can prove that the premise being true always makes the conclusion true, the argument is valid.

I don't understand what your teacher is trying to say. It's not enough to show that the argument is valid for one particular instantiation of $P$ and one particular instantiation of $C$. "Valid" means it works for all instantiations. Also, the examples of $P$ being "I am thirsty" and $Q$ being "I drink some water" doesn't work.  There are situations where you are thirsty but you don't drink water (maybe you drink nothing; maybe you drink juice), and situations where you're not thirsty but you do drink water (maybe you're Mark Zuckerberg at a Senate hearing), as well as situations where you're thirsty and drink, or not thirsty and don't drink.


How to avoid monochromatic cycles? I am working on the following exercise:

Consider a simple and connected undirected graph $G(V,E)$. Show that one can colour the edges of $G$ in polynomial time and with as few colours as possible such that there is no monochromatic cycle in said colouring of $G$.

EDIT 1: OK, my approach turned out to be false. I will leave it here for the sake of completeness. Now I have no idea how to solve this exercise. I guess the following theorem might be helpful:

Theorem: For any undirected simple graph $G(V,E)$ we can decide whether the edge chromatic number is less than $3$ and if yes we can find this optimal colouring in polynomial time.

EDIT 2: I have reread my lecture notes. This exercise is probably meant to be solved with tools from matroid theory. I just do not see how.

My WRONG approach:
I think that 2 colours should be sufficient. (Remember that this is not the classical edge colouring problem, we just want to avoid monochromatic cycles.) My first idea is to formulate a simple greedy algorithm:

Colour all edges in red.
Check the graph for cycles. If there is a cycle delete one edge of the cycle from the graph. Repeat this step until there are no more cycles in $G$.
Colour the deleted edges in blue.

However, the problem with this approach is that the blue edges may form a cylce as the example below shows. While the example below can easily be fixed by recolouring two edges I am not sure if this fix works in general. Could you please give me a hint?

What you are trying to do is find the arboricity of the graph, or equivalently compute the minimum partition into independent sets in the graphic matroid. This problem (for a general matroid) is known as the Matroid partitioning problem, for which polynomial-time algorithms exist.
You can find more details in Harold N. Gabow and Herbert H. Westermann, Forests, frames, and games: Algorithms for matroid sums and applications.


Multi-threading : N cores = N times one core? This question is about modern CPU architectures and multi-threading. I'm mainly interested in personal computers or servers having 2, 4, 8, 16... cores like for example an Intel core i7. I mean not a NASA supercomputer or GPU vector processing.

You have N cores.

You write an algorithm in a low level language such as C, C++, Java, C#... using essentially arithmetic (+/x/and/or...), basic for loops, floating point and arrays. It is mono threaded and your algorithm takes say 1 minute to complete.

Now you start N threads, and run the same algorithm on each of these threads INDEPENDENTLY : no lock (semaphores) or write access to common objects. Does each thread take 1 minute to complete, so that the total running time is 1 minute ?

What prevents this from being as good as it ? I know for example that if the threads write on the same parts of the memory (even without needing locks), the CPU caches of each processor need to refresh and the whole thing can be slowed down a lot.

Do you know some of the classical cases where the situation might be significantly different from "each thread one minute" and explain what about the architecture causes this ?

Note : Intel (for example) often uses hyperthreading so that 4 cores appear to be 8 logical processors. I don't want to focus on hyperthreading and I would like to simplify my question as if hyperthreading didn't exist. Imagine that each core can process the instructions of a single thread at a time.

I'm of course interested by things I might not be aware of in modern CPU architecture.

If I understood your question correctly, you are essentially asking:

  Given a piece of sequential code, if we run N instances of it in parallel on N cores (on real, modern, typical, and not-particularly-high-end CPU models), should we expect any slowdown versus running only a single instance of that program on a single core?

As usual, the answer is: it depends. However, the answer will often be yes indeed, you should expect a slowdown. It will often take more than "one minute" per instance.

How and why? Intuitively, since you've got shared (and limited) resources, your threads will naturally compete for them.

For instance, main memory will be shared. Thus, if your program is bandwidth-bound (which is very common across many applications), few threads can easily fully saturate your limited memory bandwidth (essentially, they can request data from memory at a faster pace than your hardware can support) and you may notice degradation in performance (given your "one minute" measure) beyond that limit. You may want to look up the bandwidth-wall problem.

For another similar instance, many modern CPU models will have a shared last-level cache per chip/socket. These (typically L3) caches will often provide significantly higher bandwidth and lower latency for any thread (on the chip) accessing any cached data, in comparison to directly accessing main memory. Once threads start competing for this shared resource, the total working set size of all thread may exceed the cache capacity -- even though a single thread was running within cache. They effectively thrash the cache for each other.

You may want to contrast these cases to the case where the program is compute-bound and CPU-intensive yet can work with high locality in the smaller, private (i.e., not shared) caches. There are probably non-memory-hierarchy reasons as well (unlike the two above), although the reasons above are perhaps among the most obvious and most significant (or, at least, that is what I would expect).


Shortest Non-Subsequence String With Constant-Size Alphabet Let $S[1..n] \in \Sigma^*$ be a string of $n$ symbols over the alphabet $\Sigma$ where $|\Sigma| \in \mathcal{O}(1)$. Determine a shortest string which cannot be obtained from $S$ by deleting some (possibly no) symbols.

For instance, we are given $\Sigma = \{ A, C, G, T \}$ and $S = ACGTACGT$. In this case, one valid answer is $CCA$, because it does not occur as a subsequence in $S$ (i.e. cannot be obtained by removing some of the symbols from $S$) and there is no such string of length $2$.

I am looking for an algorithm which takes $\mathcal{O}(n)$ or $\mathcal{O}(n \log n)$ time. It is not sufficient to compute the length of the answer, an example should also be constructed.

Observations and Approaches. The length of the answer does not exceed $\displaystyle \frac{n}{|\Sigma|} + 1$ by pigeonhole principle. This upper bound is attained for $S = ACGTACGT...ACGT$ in the above example. If we are only interested in the length of the answer, the following approach should work. Let $f(i)$ denote the largest $k \in \mathbb{N}$ such that every string of length $k$ is a subsequence of the prefix $S[1..i]$. Our final answer is $f(n) + 1$ and $f$ can be computed by dynamic programming in $\mathcal{O}(n)$ time for $1 \le i \le n$ simply by recurrence

$\displaystyle f(i) = 1 + f\left(\min{(\ell(i, \sigma_1), \ell(i, \sigma_2), \dots, \ell(i, \sigma_{|\Sigma|})) - 1}\right)$

where $\ell(i, \sigma)$ denotes the last occurrence of $\sigma \in \Sigma$ in the prefix $S[1..i]$. Obviously, the function $f$ is increasing, i.e. $f(i + 1) \ge f(i)$ for $1 \le i \le n - 1$. It seems more difficult to construct an example from this information, that is where I am stuck.

Finally note that the problem is a lot easier, if we require the subsequence do be contigous. Since there are only $\mathcal{O}(n^2)$ substrings, but $\mathcal{O}(|\Sigma|^k)$ strings of length $k$ over $\Sigma$, $k$ turns out to be very small and even brute-force will succeed.

Any kind of help is appreciated, thanks in advance.

Original Source: CSES Problem Set (https://cses.fi/problemset/task/1087/).

For each $i$, let $s(i)$ be a string of length $f(i)+1$ that is not a subsequence of $S[1\ldots i]$, then what you seek for is exactly $s(n)$. Also denote $g(i) = \min\left(\ell\left(i,\sigma_1\right),\ldots,\ell\left(i,\sigma_{|\Sigma|}\right)\right)$. $g(i)$'s can be computed in $O(n)$ time in advance.

We have
$$
s(i)=s(g(i)-1)S[g(i)].
$$
Firstly $s(g(i)-1)S[g(i)]$ is of length $f(i)+1$. Suppose by contradiction $s(g(i)-1)S[g(i)]$ is a subsequence of $S[1\ldots i]$, then the index that the last character $S[g(i)]$ matches must be less than or equal to $g(i)$, which means $s(g(i)-1)$ is a subsequence of $S[1\ldots (g(i)-1)]$, a contradiction. So the recurrence is correct.

Now you can use this recurrence to compute $s(n)$:

Let $i \leftarrow n$, and let $s$ be an empty string.
If $g(i)$ does not exist, which means there is at least one character not appearing in $S[1\ldots i]$, insert this character to the beginning of $s$ and return $s$.
Insert $S[g(i)]$ to the beginning of $s$.
Let $i\leftarrow g(i)-1$.
Go back to step 2.


Paper-based algorithm to find longest formula which is common to at least two formulas Given a list of logical formulas:

f1: A&B
f2: A&D&C
f3: B&D&E
f4: A&B&C
f5:
fn: ...

In this case I want A&B as the longest formula which is common to at least two formulas.
Is there a simple algorithm to find the longest formula that could be performed on paper?

For each pair of formulas $f_i,f_j$ from your list, find the longest formula common to both $f_i,f_j$.  If things are as in your example, this is as simple as a set intersection.  That gives you $n(n-1)/2$ candidates.  Take the candidate that is the longest.


Why isn't the time complexity of constructing a Fenwick tree tighter than $O(n\lg n)$? Intuition:

Suppose I have an array of nonzero integer values $A[n]$ and a partially constructed Fenwick tree of this array: $F[k], n>k$. I can see why inserting the next element would be worst case $O(\lg n)$. The number of elements accessed from $F[0:k]$ to calculate $F[k+1]$ is equal to the number of trailing zeroes in $(k+1)_2$ which is at most $\lfloor \lg(n) \rfloor$. There are $n$ elements, so this is $O(n\lg n)$. Wikipedia seems to agree as well.

Thoughts:

NOTE: I am using this algorithm.

Consider the number of positive integers less than or equal to $n$ with exactly $j$ trailing zeroes in their binary representation, $j<{\lfloor \lg(n) \rfloor}$. Since the leftmost ${\lfloor \lg(n) \rfloor}-(j+1)$ digits can be freely assigned so long as the resulting number is less than $n$ ($j+1$ because the $(j+1)th$ digit from the right must be a $1$), there are between $2^{\lfloor \lg(n) \rfloor-j-1}$ and $2^{\lfloor \lg(n) \rfloor-j)}$ such numbers for any $n$.

Let an operation be defined as the summation of two numbers, which is assumed to be a constant time operation. (The other operations, like insertion, are also in constant time and are performed a constant number of times, hence they are ignored) Thus, for $j$ trailing zeroes, $j$ operations must be performed.

As a result, the total number of operations to perform is at most $\sum\limits_{j=0}^{\lfloor \lg(n) \rfloor} j2^{{\lfloor \lg(n) \rfloor}-j}$. It must also be true that $2^{\lfloor \lg(n) \rfloor}≤n<2^{\lfloor \lg(n) \rfloor + 1}$. Note that both maxima occur when $n_2$ is filled with ones. If we take this case, the mean number of operations for any $j$ as $n \rightarrow \infty$ should be:

$\lim_{n\to\infty}\frac{\sum\limits_{j=0}^{\lfloor \lg(n) \rfloor} j2^{{\lfloor \lg(n) \rfloor}-j}}{2^{\lfloor \lg(n) \rfloor +1}-1}
=\lim_{n\to\infty}{\sum\limits_{j=0}^n \frac {j}{2^{j}}}
=1$

Now, if we take the other extreme, where $\lg(n)\in\mathbb{Z}$ ($n_2$ is a one trailed exclusively by zeroes) then there are exactly $\lg(n)+\sum\limits_{j=0}^{\lg(n)-1} j2^{{\lg(n)-1}-j}$ operations to be performed over exactly $2^{\lg(n)}$ numbers, and the limit also approaches $1$. Testing seems to reveal that no other values of $n$ with the same $\lfloor \lg(n) \rfloor$ values have a higher mean number of operations per element than these.

If the amortized cost of inserting each element is indeed constant, shouldn't constructing the tree be $\Theta(n)$ time?

Testing:

I've tested the ranges between admittedly small consecutive powers of two, both by applying the summation and by brute force, and the results seem to agree:

Code using summation: http://pastebin.com/T3EEM7qz

Code using brute force: http://pastebin.com/sxdAkgxn

Technically it is $O(n\log n)$, since big-O is an upper bound only, but your tighter bound of $O(n)$ is also correct.  (Without loss of generality, it suffices to restrict $n$ to powers of two; then the proof is easy.)


What is the literature on a sparse matrix encoding of rose trees? I have 'discovered' a way to encode rose trees (see e.g. What are the applications of Rose trees? ) as a sparse matrix: if you have a node n with ID i and parent ID p, then you place n in the matrix at coordinates (row, column) of (p, i). This makes it easy to:

Get a node by its ID and parent ID (single lookup of the matrix)
Get all children of a node ID (lookup a matrix row)
Prune and graft subtrees (change the coordinates of the subtree root)

Now I'm thinking that I can't be the first person to have thought of this. Can anyone point me to any literature which discuss this encoding?

In view of rose tree being just a special case of a graph,
the matrix representation you mentioned is simply the adjacency matrix representation of directed graph. Your particular encoding takes the rose tree's edge to always be directed consistently either from parent to child or child to parent.

Questions about rose tree in this encoding thus can be researched easily by looking up results about adjacency matrix representation of directed tree graph.

Relevant notions are:

get all leaves of subtree -> reachability
graft tree -> wedge sum


Intuition behind the Reversal Algorithm [ Rotation of Array ] I know that the below program uses Reversal algorithm to rotate an array's elements to k positions to the right. But how does the Reversal algorithm works? It seems kinda magic to see. Can somebody give me the intuition or simple math explanation for me to understand.
void rotate(vector<int>& nums, int k) {
    k %=nums.size();
    reverse(nums.begin(), nums.end());
    reverse(nums.begin(), nums.begin()+k);
    reverse(nums.begin()+k, nums.end());
}

Imagine flipping a deck of cards over, then dividing it into two parts and flipping each part over. The cards in each part end up in their original order because they're flipped twice. The first flip also swaps the two parts. The net effect is the same as cutting the deck, i.e. rotating it.


Understanding basic queue and dequeue operations CLRS gives the following implementation for a queue's enqueue and dequeue operations

head = 1
tail = 1

ENQUEUE(Q, x)
Q[Q.tail] = x
if Q.tail == Q.length
    Q.tail = 1
else Q.tail = Q.tail + 1

DEQUEUE(Q)
x = Q[Q.head]
if Q.head == Q.length
    Q.head = 1
else Q.head = Q.head + 1
return x

but I'm having trouble understanding why both

if Q.tail == Q.length
    Q.tail = 1

and

if Q.head == Q.length
    Q.head = 1

are needed. What would be a conceptual (or possibly visual) explanation of these two if-statements?

CLRS defines a queue using an array which wraps around i.e when we no longer can insert/delete in the last position, we move to the first position.

From the book,

  The elements in the queue are in locations head[Q], head [Q] + 1, . . . , tail [Q] - 1, where we "wrap around" in the sense that location 1 immediately follows location n in a circular order.

Thus,

  if Q.tail == Q.length

This is for the condition when the tail points to the last element.

  if Q.head == Q.length

This is for the condition when the head points to the last element.

In both cases, we move to the first element due to circular nature.

An example would be this:


Why cannot we reduce the Emptiness problem of LBA to the Acceptance problem of LBA? I am a little bit confused about the emptiness problem of the linear bounded automaton (LBA). I know that this problem is undecidable. However if we assume that is decidable, what could be wrong if we reduce it to the acceptance problem of LBA?

Since the acceptance problem for LBAs is decidable, if you could reduce th emptiness problem to the acceptance problem, then the emptiness problem for LBAs would be decidable. However, the emptiness problem for LBAs is not decidable. This shows that we cannot reduce the emptiness problem to the acceptance problem.

It seems that you are confused about the direction of the reduction. When reducing problem A to B, we show how to solve problem A using problem B, not the other way around.


Longest path among subset of given points I am looking for an efficient algorithm to solve the following problem:

Given $n$ points in 2D Cartesian space $p_1,\dots,p_n \in \mathbb{R}^2$ and an integer $m$, we want to find $s_1,\dots,s_m$ such that $1 \le s_1 < s_2 < \cdots < s_m \le n$ and that maximizes

$$\sum_{i=1}^{m} \|p_{s_i} - p_{s_{i+1}}\|_2,$$

where $\|p-q\|_2$ represents the $L_2$ distance between two points.  In other words, we want to find a subsequence of the points $p_1,\dots,p_n$ such that the distance of following that path is maximized.

Is there an efficient algorithm for this problem?

In my application $m$ is at least 3 orders of magnitude smaller than $n$ and neighboring points $p_i,p_{i+1}$ are close to each other, which makes the search space structured.  I have tried simulated annealing with and without an adaptive neighbourhood and get decent results, but I want to know if there is a optimal algorithm.  Does anyone know other algorithms and ideally their complexity?

This can be solved exactly with dynamic programming. The running time will be $O(n^2m)$.  It finds the exact optimal sequence, not just an approximation.

Let $A[t,u]$ denote the longest path $p_{s_1},\dots,p_{s_t}$ such that $s_t=u$.  In other words, it is the maximum possible value of $\|p_{s_1} - p_{s_2}\|_2 + \dots + \|p_{s_{t-1}} - p_{s_t}\|_2$ such that $1 \le s_1 < \cdots < s_t = u$.

Notice that we have a recursive equation that defines $A[\cdot,\cdot]$.  In particular,

$$A[t,u] = \max \{ A[t-1,v] + \|p_v - p_u\|_2 : 1 \le v < u\}.$$

Thus, we can fill in the values of $A[t,u]$ incrementally, in order of increasing value of $t$.  Each step requires $O(n)$ time, and there are $nm$ entries to fill in, so the total running time is $O(n^2m)$.

In practice the running time might often be something closer to $O(nm)$ if you terminate the search for $v$ early.  In the recurrence above you might often be able to prove that  if $v$ is much smaller than $u$ the maximum can't be achieved, so you could examine at values of $v$ in decreasing order and stop the iteration early once you know there is no improvement possible with a smaller value of $v$.


Return destinations for an expression-oriented programming language I am designing a programming language and I want to give everything the ability to return a value. For example, if I use a block as a right-hand side value, I can assign it to a lvalue:

sum := {
    if (a < 0) { a := -a; }
    if (b < 0) { b := -b; }
    return a + b;
};

Also, if and while statements could return a value, and there is no need for something like a ternary operator then.

After a bit of research, I have found that Rust is capable of doing this. And this is great for language design, because it significantly reduces the number of language constructs needed. You don't really need a do-while loop, as that's just a while loop with a braced condition:

do {
    foo();
} while (a > 0);

Is equivalent to:

while {
    foo();
    return a > 0;
}{}

Also, with ignored variable bindings, you can create continue and break statements for loops:

// Break
_ := while (a > 0) {
    if (a == 5) {
        return ();  // Empty tuple
    }
    a += 1;
};
// Continue
while (a > 0) { _ := {
    if (a == 5) {
        return ();  // Empty tuple
    }
    a += 1;
};}

I like the idea of having less language constructs, because the language is expressive enough to do this without labeling and goto statements.

But as I was thinking about this, two things popped into my head:

Are these just very abstract lambda expressions?
How could the 'return destination' be labeled so we can return from a very nested expression even right out to the function? I think I would probably need some extra notation for that.

1) In a sense, yes. Guy Steele wrote the "Lambda papers", where he reduced many different constructs to lambda expressions, in a compositional way. He used the lambda abstractions of Scheme for this, but the construction is general.

2) You should read about continuation passing style. Scheme, for instance, uses  "call with current continuation" call/cc to achieve what you describe: "returning" from a deeply nested location.

call/cc is probably not the most convenient notation, but it works, and can be used with any expression. E.g.

(call/cc (lambda (k)
  (+ 1 (if (some-condition) 10 (k 2)))

Above, if the condition is true, the if evaluates to 10, which is added to 1, so that the whole result is 11. If it is false, (k 2) is evaluated, "returning" to the point call/cc was used with result 2. Note that this skips the (+ 1 ..) part. You can nest call/cc arbitrarily, providing many "return points" as wanted.


Calculation of effective average instruction execution time in a 2-level paging system System has a two level paging scheme
  Average CPU time for a instruction = 100ns
  Average number of memory accesses per instruction = 2
  Regular memory access = 150 ns
  Page fault service time = 8ms
  TLB hit ratio = 0.9
  Page fault rate = 0.0001

  What is the average instruction time if the time required for address translation is negligible?

I worked out the solution as follows

Average instruction execution time = CPU time + Memory access time

Memory access time = No. of memory accesses by the instruction * average memory access time

Average memory access time =
 [probability of a TLB hit * regular memory access time]
 + [probability of a TLB miss * (Time for accessing the 1st level of the paging tables
     + Time for accessing the 2nd level of the paging tables
     + Time for accessing memory which may not be paged in with the translated address)]

Time for accessing the 1st level of the paging tables
= Time for accessing the 2nd level of the paging tables
= Time for accessing memory which may not be paged in with the translated address
    = [probability of a page fault * (page fault service time + regular memory access time) ]
      + [probability of no page fault * regular memory access time]
    = [0.0001 * (8 ms + 150ns)]  + [0.9999 * 150 ns]
    = 950 ns

Thus, average time per memory access = [0.9 * 150ns] + [0.1 * 3 * 950ns] = 420ns

Average instruction execution time = 100ns + (2 * 420ns) = 940ns

However the choices for this question are 645ns, 1050ns, 1215ns and 1230 ns.

I can't seem to be able to see where I have reasoned wrong.

EDIT

Average number of memory accesses per instruction is 2

I think the question wants you to assume that only about 30% of instructions involve a data memory access (which is somewhat low even for a RISC, Hennessey & Patterson give 47% for MIPS for 5 SPECint2000 benchmarks).  100ns + (1.3 * 420ns) = 646.

(Unless the average number of memory accesses per instruction was provided elsewhere, this question is technically unanswerable; but guessing that the number is less than two per instruction [e.g., a load-store ISA and not a memory-memory ISA] might be reasonable.)


Correctness of Algorithm for Computing Diameter of a Graph I am a TA for an introductory CS course, and one question given to students was how to use BFS to determine the diameter of a graph. The students were told they wouldn't be graded for efficiency, so the expected answer was a brute force algorithm where they ran BFS from every node to every other node and returned the maximum distance from these BFS runs. The students were provided with a BFS method they could reference in their pseudocode which took as an input a node and returned two mappings: one from each node in the graph to its distance from the start node (called distmap), and one from each node to its 'parent node' along the shortest path from the input node (called parentmap).

One student wrote the following algorithm:

1. Choice an arbitrary node from the graph and run BFS from it.
2. Create a set Temp of all the nodes that are not values in parentmap (ie nodes which don't lie upon any shortest paths)
3. Initialize max_dist to 0
4. For each node n in Temp:
    5. Run BFS from n
    6. For each value d in distmap:
        7. IF d > max_dist THEN set max_dist equal to d
8. RETURN max_dist

I believe this answer is correct, but I am unable to prove it. Can someone prove why it works or provide a counterexample?

It works for trees (although it can be simplified).  However, on general graphs it does not work.

If your arbitrary vertex $v$ is the one on the top (labeled 1), then the Temp={8,9}.  However, the unique diameter path is from 7 to 6.


Relation between number of edges and vertices in a DAG I conjecture that, in a Directed Acyclic Graph, $O(|V|) = O(|E|)$. Is this statement correct, can it be refined? This is probably standard material; is there a simple reference about this?

The maximum number of edges in a DAG with n vertices is $\Theta(n^2)$.

Refer https://stackoverflow.com/questions/11699095/how-many-edges-can-there-be-in-a-dag


Running time and stack depth of a lisp recurrence Consider the following sequence $a_n$:

\begin{align*}
  a_0 &= \alpha \\
  a_k &= \beta a_{k-1} + \kappa
\end{align*}

Now consider the implementation of this sequence via lisp:

(defun an (k)
  (if (= k 0) alpha
    (+ (* beta (an (- k 1))) kappa)))

What is the running time to compute (an k) just as it is written? Also, what would be the maximum stack depth reached? My hypothesis would be that both the running time and stack depth are $O(k)$ because it takes $k$ recursive calls to get to the base case and there is one call per step and one stack push per step.\
.

Is this analysis corect?

The time and other resources (such as stack consumption) needed to run an with the argument $x \in \mathbb{N}^*$ is the sum of:

the resources needed to compute (- k 1) with k bound to $x$;
the resources needed to compute an with the argument $x-1$;
the resources needed to compute (if (= k 0) alpha (+ (* beta $y$`) kappa))` where $y$ is the value returned by the recursive call to an.

Let $T(x)$ be the running time of this computation. For $x \gt 0$, by the analysis above, $T(x) = T(x-1) + C$ for some constant $C$ (assuming that the arithmetic operations take constant time). A very simple induction shows that $T(x) = C \, x + T(0)$, i.e. $T(x) = \Theta(x)$. The same goes for stack consumption.

There is more than one stack push per recursive call, (3 in a naive interpreted Lisp such as Emacs Lisp), but that doesn't affect the $O$ or $\Theta$ analysis. Other than this minor detail your analysis is correct.

Are you sure that you typed the right code? Emacs has a fairly low limit on stack usage but even it can sustain more recursive calls (up to 123 in Emacs 23 where max-lisp-eval-depth is 500).


relation between $\forall$ and implication in intuitionistic logic using curry-howard and propositions as types I am currently trying to wrap my head around intuitionistic logic and its interpretation using the curry-howard isomorphism and propositions as types.

I came about this explained relation between $\forall$ and $\rightarrow$:

  A function type $s \rightarrow t$ is actually a function type $\forall
 x:s.t$ where the variable x does not occur in t. [..] Moreover, if we
  have a type $\forall x:s.t$ where x does not occur in t, we can omit x
  and just write $s\rightarrow t$ without losing information.

I do not get how this can work as I understand a $\rightarrow$ basically as "give me a proof of s and I give you a proof of t" - a mapping function. However, a function that maps needs a parameter, in this case the x which is a proof of s : $f(x):s\rightarrow t$. How can I still have a mapping if I am 'not allowed' to use x and thus any information contained in it anymore?

If I use an example: e.g. proof that every $\mathbb{N}$ is $\mathbb{R}$ I need to use the information contained in the proof that a given number is in $\mathbb{N}$ to show that $\mathbb{N}$ is more restrictive than $\mathbb{R}$ and thus any $\mathbb{N}$ has to be $\mathbb{R}$. However, I do not have 'access' to those information as x (the proof that the number is in $\mathbb{N}$) does not occur in my proof that the number is also $\mathbb{R}$.

The difference between $s\to t$ and $\forall x : s. t$ is that in the second case, the return type of the function depends on the input.

For example, in most languages, you can make a function that takes a natural number and returns an array of that size and it will have type $\operatorname{nat} \to \operatorname{nat} \operatorname{array}$. But if you want to specify it further and say that it doesn't return any array but really an array of that size, then you would want to type it as $\forall n :\operatorname{nat}. \{a : \operatorname{nat} \operatorname{array} | \operatorname{size}(a)=n\}$. In both cases the output of the function (the array of size $n$) depends on the input $n$ of the function but in the second case, the return type $\{a : \operatorname{nat} \operatorname{array} | \operatorname{size}(a)=n\}$ also depends on the input while in the first case it does not.

Another example would be a function that takes a proof that $m=2$ and returns a proof that $m\le 2$. All it has to do it use the reflexivity of $\le$, which I'll call $\operatorname{le\_refl}$. You can define $(\lambda (m:\Bbb N).\lambda (p:m=2).\operatorname{le\_refl}(p)):\forall (m:\Bbb N).(m=2\to m\le 2)$. Note that you could also write the type as $\forall (m:\Bbb N).(\forall(p:m=2). m\le 2)$ but since the return type $m\le 2$ of the inner function doesn't depend on the proof $p$ (even though its output does), you can simplify it and use the arrow notation.

Yet another way to think of is that $\forall(x:A).B(x)$ (where I write $B(x)$ instead of $B$ to emphasize that it can depend on $x$) is often written $\Pi(x:A).B(x)$ in type theory. And it makes sense because in a way, this expressions gives you a way to define a type $B$ given $x:A$. And the you look at the set of all functions that take an input $x:A$ and return an element of $B(x)$. Now think of the cartesian $\prod_{x\in A}B(x)$ product of the elements of the set $\{B(x)|x\in A\}$. An element of that is a big tuple indexed by $A$ and if you ask the element in the spot $x\in A$, it gives back an element that's in $B(x)$. So it's the exact same thing. Also note that when you take $B$ to be constant, you get $\prod_{x\in A}B$ which is usually denoted $B^A$ or $A\to B$.


Is the set of all valid C programs countable? Is the set of all syntactically valid C programs countable or uncountable?

Infinite. Countable. Given a length $l$, and a finite number of characters, $c$, we know that each length has only finitely many possible valid c codes $c^L$. We can easily make a bijection from the natural numbers to the lengths, and at each length we add only finite number of other valid code, thus countable.


CSP Forward checking with n-ary (and binary) constraints I have implemented my own CSP solver using a Backtracking algorithm.
Within the Backtracking algorithm I apply a Forward Checking algorithm (reducing domains of connected, unnasigned variables) that only works with Binary constraints.

The problem I have is that the CSP I try to solve has lots of n-ary constraints, making the FC algorithm mostly redundant.

Is there a way to enhance or replace my FC algorithm, so it works with n-ary constraints.
Or is there a "simple" procedure to convert n-ary constraints to binary constraints?

EDIT:
Added pseudo code (attempt) of the Forward Checking algorithm:

function ForwardChecking(variable, csp) list of variables with new domains, or failure
    for each constraint in connectedConstraints(variable) do
        if connectedVariable is assigned then
            if constraint is not satisfied then
                return failure
        else
            for each value in connectedVariable.domain do
                connectedVariable.assign(value)
                if constraint is not satisfied do
                    remove value from connectedVariable.domain
                if connectedVariable.domain.count == 0 then
                    return failure
                add connectedVariable to solution
    return solution

Instead of forward checking, try arc consistency. You run arc consistency after every assignment to reduce backtracking.

Another further improvement would be assigning a least constraining value (LCV) to a variable with minimum value in the domain (MRV).


Finding longest prefix of a given string in set of strings that satisies some property I have a set of strings, lets call them RULES. I have a function F which given 2 strings deterministically returns boolean value. Given one string, lets call it QUERY, what is the fastest way to find longest prefix (lets call it P) of QUERY which is a member of RULES for which F(P,QUERY) returns true?

That was very generic definition of a problem. The reality is that I have a huge tree of objects. Each object has one of predefined types. I want to have a way to define different views on that tree. Each view is set of rules describing which types of objects are (in)visible in subtree subtree described by that rule. Basically a rule is a pair - path/prefix in tree and map from type to boolean. An object of type T is visible via given view iff the longest rule that has path that is prefix of that objects path has true as an entry for type T.

An example:

Types are {A,B,C}.

Tree contains those objects: /A1, /A2, /A1/B1, /A1/C1, /A1/B1/C1, /A2/B1, /A2/C1

View is defined by those rules: {/; C=>true, A=>true}, {/A1/B1; C=>true}, {/A1; C=>false}, {/A2; B=>true,C=>true}

Objects visible via that view: /A1, /A2, /A1/B1/C1, /A2/B1, /A2/C1

Right now I'm solving this by storing all rules for view in (hash)map - key is path and value is set of rules. When I've checking given object, I start from its full path and check in a loop each of is prefixes by removing top path component and looking it up in (hash)map. When it contains entry for that prefix I check if it contains entry for the type of object - if it does I return it as value of visibility. Otherwise I continue with next shorter prefix. If no rule was found I decide that object is not visible.

I'll answer your generic question.  Store the RULES in a trie.  Then, you can generate each prefix of the QUERY, traversing the trie as you go.  This will let you enumerate all prefixes P of QUERY that are a member of RULES.  For each such prefix P, you can then evaluate F(P,QUERY).  The running time is $O(n)$ where $n$ is the length of QUERY, plus the time to do at most $n$ invocations of F.  If you want, you can check the longest prefixes of QUERY first, in order of decreasing length, so that once you find a single prefix P where F(P,QUERY) returns true, you can stop immediately.

I don't believe it is possible to do better, without knowing something about F.  Obviously, any algorithm must take at least $\Omega(n)$ time (since you must read each character of QUERY), and must invoke F potentially on each prefix that is a member of RULES.


Proving a CFG is ambiguous? I have a CFG:

S --> 0S1S | 1S0S | ε

I'm trying to prove that it is ambiguous, but the steps to proving so are confusing me.

So if I pick a string, let's say 010110, I just have to show that there are two different parse trees for the string?

Proving inherent ambiguity of a language is difficult, but proving ambiguity of a grammar is relatively quite easy.

The definition of ambiguity of a grammar does not say that every string has to have different parse trees. It says there need to exist only one string which has different parse tree to make a grammar ambiguous.

The trick to achieve two different parse tree for an ambiguous grammar is to look for a string where you can apply two different rules for the same string or the same rule in two different ways. Since one rule derives $0S1S$ and the other rule derive $1S0S$ you cannot have both rules deriving same strings, so you have to look for a rule that can be applied in two different ways. There you are in luck. Both rules can be applied in different ways.

Take first rule for example: $S \rightarrow 0S1S$. Can you have a string starting with 0 but matches 1 at two (or multiple) different places? It turns out you can $\underline 0$-$10$-$\underline 1$-$\epsilon$ and $\underline 0$-$\epsilon$-$\underline 1$-$01$ i.e. string $0101$. $0101$ and $1010$ are the smallest length strings of the grammar which will have different parse trees.

String $010110$ also has two parse trees $\underline 0$-$\epsilon$-$\underline 1$-$0110$ and $\underline 0$-$10$-$\underline 1$-$10$.


Finding the best combinations between items of 2 arrays in a sequential manner I'm reposting this because people found the last description to be too hard to follow.

The data unit I'm working with is a pair of 2 numbers. The numbers can be any integer that is bigger than 0. Example: [X, Y]
The input is 2 arrays of these pairs, each array can have any length. Example:  A = {[1, 2], [3, 2], [5, 1]}  B = {[2, 3], [4, 5], [5, 3]}
If I combine 2 pairs, one from each array, I get a new pair like this: [X1, Y1] + [X2, Y2] = [X1 + X2, Y1 + Y2]
The output is a result of all combinations between the elements of the 2 input's where each element is the "best" and is ordered as ascending by Y

What "best" means in this case is that given [X, Y],

this pair would have the highest or equal to highest X compared to all the other pairs that might have the same Y Example:
[2, 2], [2, 2],[1, 2]
it cannot have an X equal or lower than the maximum of any other pair that has a lower Y Example: [2, 1], [4, 2],[2, 4]

To illustrate how the output can be reached

Lets take this example input:  A = {[1, 2], [3, 2], [5, 1]}  B = {[2, 3], [4, 5], [5, 3]}
First we combine every item in A with every item in B
A[1] + B[1] = [3, 5], A[1] + B[2] = [5, 7], A[1] + B[3] = [6, 5]
A[2] + B[1] = [5, 5], A[2] + B[2] = [7, 7], A[2] + B[3] = [8, 5]
A[3] + B[1] = [7, 4], A[3] + B[2] = [9, 6], A[3] + B[3] = [10, 4]
Next we order the combinations by Y
[7, 4], [10, 4], [3, 5], [6, 5], [5, 5], [8, 5], [9, 6], [5, 7], [7, 7]
Filter the combinations by the rules described above  [10, 4]

So in this example, the output is an array with the length of 1 because all other pairs with Y of 4 have lower X and all other pairs with Y > 4 have equal or lower X.

I didn't include it in the example because its not necessary but the process can be optimized by prefiltering A and B by the same rules.

Now to my problem: I'm not dealing with arrays with the length of 3 but rather several hundred and the input count isn't 2 but 5+, as you can imagine, this process can be nested like this: result5 = process(process(process(process(A, B), C), D, E)

So in practice, the potential memory use is A.size * B.size * C.size * D.size * E.size.. which is a lot more than fits in the 20something kB i have available.

What I'm looking for is an algorithm that will fetch me the same results, in the same order, one by one. The fetches will be sequential and will start from 0 so I think any algorithm that can produce all the results in the right order without sorting in the end can be modified for this. Does anybody know how this could be achieved?

Negate the Y values.  Then you are looking for the Pareto-optimal frontier of the set of combinations.

There are standard algorithms for computing the Pareto-optimal frontier of any set.  In particular, see the last part of this answer for an overview of algorithms (the simple cull algorithm, divide-and-conquer, and hybrids between those two).  Those algorithms should be much more efficient than what you were considering before.  For example, the simple cull algorithm has $O(n^2)$ running time to compute the Pareto-optimal frontier of a set of size $n$ (or $O(nm)$ time, if you know the output is of length $m$).

Here's how you can use this in your setting.  First, compute the Pareto-optimal frontier of A and the Pareto-optimal frontier of B.  Then, enumerate all combinations of those two frontiers.  Finally, compute the Pareto-optimal frontier of that list of combinations.  If you use the simple cull algorithm, the running time will be at worst $O(n^4)$, where $n$ is the length of the input lists.  If the output has size $m$, the running time will be at worst $O(n^2 m)$.  In either case, the memory consumption will be $O(n^2)$.  The algorithms might perform better than that in practice, depending on your data.

If you want the output to be in sorted order, you can sort by Y value after computing the set.

I would recommend that you try these algorithms and see what the memory consumption looks like.  If the memory consumption is still too much, then you can let us know.


Clarify the steps: what happened in this mathematical modelling of TSP? Source: http://examples.gurobi.com/traveling-salesman-problem

I don't get this part: (look at the source)

  $$\sum_{i,j\in\{1,2,3\},i\neq j} x_{ij}=3>2=|\{1,2,3\}|-1$$

I get that $x_{ij}$ is equal to 3, but why the "> 2" ?

And what is the deal with subtracting 1 from a set? How do you even do that?

How come $|\{1,2,3\}|-1 = 3 > 2$   ?!?

Okay so:
$$|\{1,2,3\}|-1 = 2$$

So how is he allowed to write:
$$|\{1,2,3\}|-1 = 3 > 2$$

?

That is basically the same as writing: (which is incorrect right?) $$2 = 3 > 2$$

I don't get this part at all, please elaborate on what happened in as simple language as possible. My level is high school final math level.

You seem to have misunderstood pretty much every part of the statement

$$\sum_{i,j\in\{1,2,3\},i\neq j} x_{ij}=3>2=|\{1,2,3\}|-1\,.$$

  I get that $x_{ij}$ is equal to 3,

No, the sum of all values $x_{ij}$ where $i$ and $j$ are distinct values from $\{1,2,3\}$ is equal to $3$.

  but why the "> 2" ?

Because three is bigger than two.

  And what is the deal with subtracting 1 from a set? How do you even do that?

No, it's subtracting one from the cardinality of the set. Notice the $|\dots|$.

  How come $|\{1,2,3\}|-1 = 3 > 2$   ?!?

It isn't. When we write something like $A=B>C=D$, it means that $A=B$, $B>C$ and $C=D$. You can't just re-order the terms and expect the statement to remain true, just as you can't reorder $3>2$ as $2<3$ and expect it to remain true.

So, the statement as a whole means:

The sum of the values $x_{ij}$ is equal to $3$.
Also, $3>2$.
Also, $2=|\{1,2,3\}|-1$.

  So how is he allowed to write:
  $$|\{1,2,3\}|-1 = 3 > 2\,?$$

He isn't and he doesn't.


Finding Kernel in DAG Let $G=(V,E)$ be a DAG. A subset $A \subseteq V$ is called a kernel if for all $u,v \in A$ $uv \notin E$ and for all $v \in V-A$ there exists an $a \in A$ such that $av \in E$ (note again, this is a directed graph).

I need to find an algorithm that runs in $O(V+E)$ that upon giving a DAG $G$, would find a kernel in the graph.

I started like this:

Sort the graph toplogically. Such a sorting exists since it is a DAG. Let us mark the output as $v_1, v_2,...,v_n$. Then we run right to left:

If $v_n$ has no ingoing edges, we add it to our kernel set $K$. Else, here I got stuck.

Maybe dynamic programming can help us here?

Let's start the algorithm with these 3 sets:

$V$ = {all vertices}
$K$ = {}
$K'$ = {}

with the semantics:

$V$ stores unprocessed vertices
$K$ stores vertices known to be in the kernel
$K'$ stores vertices known to be outside the kernel

You're right that all vertices without incoming edges always belongs to the kernel. Add the them to the set $K$ & remove from $V$.

The next step is realizing that any vertices that can be immediately reached from vertices in the current $K$ must be outside the kernel. Add these to $K'$ &  remove from $V$.

Now, all the vertices that is left in $V$ without incoming edges (from other vertices inside $V$) again can be added to $K$ (and remove from $V$).

...

Repeat the process until $V$ is empty.


Sieving to compute first values of totient function What i want to do is to compute the first $n$ values of Euler's totient function effectively. As far as i know the best way to do it is to run a sieving algorithm and for each prime encountered to update current totient-value for all its multiples. My realization in Python is given below. I use two facts about totient function:

a) if $~p~$ is prime than $~\phi(n) = n-1$

b) for any prime $~p~$ and positive integers $~a,n~$  $~\phi(p^a n) = p^a n (1 - \frac{1}{p})$

My problem is termination of main loop. My code loops till $n / 2$  though i would like to stop at $\sqrt{n}$. The problem is that some numbers above $\sqrt{n}$ may have prime divisors above $\sqrt{n}$ which won't be processed with current version of algorithm if main loop is terminated before $n / 2$. I don't understand how to handle totient function values for such numbers since calculation for them wasn't finished in fact. Any ideas on these problem will be highly appreciated. Thanks in advance!

# n >= 2
def sieve(P, n):
    end = n // 2 + 1
    for k in range(2, end):
        if (P[k] == k):
            for j in range(2*k, end, k):
                P[j] -= P[j] // k

def phi(P, n):
    if (n == 1):
        return 1
    if (P[n] == n):
        return n-1
    return P[n]

n = int(input())
P = [i for i in range(0,n+1)]
sieve(P, n)
for k in range(1, n+1):
    print(repr(k) + "  " + repr(phi(P,k)))

The complete formula for Euler's totient function is
$$
\varphi(n) = n\prod_{p|n} \left(1-\frac{1}{p}\right),
$$
where the product goes over all prime factors of $n$. Hence you essentially need to factor $n$ in order to compute $\varphi(n)$. You can do it in any way you wish.

Computing $\varphi(n)$ is believed to be as hard as factoring $n$ (and is indeed as hard in some special cases, for example when $n$ is a product of two primes).

You can use a sieve to factor all numbers up to $n$. The idea is to go from $2$ to $n$; whenever encountering an uncircled number $p$ (the initial state), this number must be prime, and we can circle all its multiples. Moreover, we can divide these numbers by $p$, the appropriate numbers by $p^2$, and so on. At the end, the uncircled numbers are all primes, and all other numbers have been factored.

You can easily adapt this algorithm to compute the totient function directly. Every time you encounter a new prime $p$, you divide all its multiples by $(p-1)/p$. After going through all numbers up to $n$, all uncircled numbers are prime, and so their totient function is easy to compute.


Example of existence proof in dependent typing? I understand that $\Pi$ types are generalizations of functions and can be interpreted similar to $\forall$ in logic. I also know that $\Sigma$ types are generalizations of tuples and can be interpreted similar to $\exists$ in logic. But whereas I find it easy to imagine $\Pi$ type examples by thinking in Haskell, I am having a hard time thinking of good examples of $\Sigma$ types. Is there a particular "canonical" $\Sigma$ type that gives a good indication of how it can be interpreted as existence when the type is thought of as a proof?

$\Sigma$-types in Haskell appear in various places. Because Haskell is not dependently typed, they often reduce to the non-dependent version of $\Sigma$-types, which are just Cartesian products. So whenever you see an ordered pair, or a record, that is a simple case of a $\Sigma$-type.

At the level of a modules there can be dependencies and so we get actual $\Sigma$-types. For instance, a module which defines a type $T$ and then a value $f$ of type $T \to T$ has the kind $\Sigma_{T : \mathrm{Type}} (T \to T)$. (The module should hide the definition of $T$ in order for this to actually be the case.) Observe that this is a "large" dependent sum because it ranges over "all Haskell types $T$" so I refer to it as a "kind". In fact, the theory of modules is based on the observation that hiding bits of a program behind a layer of abstraction is precisely the same as forming a dependent sum.

Haskell has existential types. These are like depenent sums of the kind I mentioned above. Namely, an existential type

data Calf = forall t . Bull t => Cow(t)

is just a confusing way of writing $$\mathtt{Calf} = \textstyle \sum_{t : \mathtt{Bull}} Cow(t).$$ Strangely, the "forall" keywords indicates the fact that there exists a type $t$ of class $\mathtt{Bull}$ such that $F(t)$. Perhaps some Haskellites can explain the logic behind the notation to me.


Can every program be turned into a quine? Given a program $P$ which takes a binary string as input, can one always (effectively) construct a program $P'$ such that $P'(0x)$ runs $P(x)$ and $P'(1x)$ outputs the source code of $P'$? I didn't find anything with some googling, but it seems like the kind of thing that could be known.

You are looking for the recursion theorem. Let $F(e)$ be the function that on input $0x$ returns $P(x)$ and on input $1x$ returns $e$. A fixed point $\varphi_e = \varphi_{F(e)}$ is what you're looking for.

If you're interested in how this quine is constructed, take a look at the proof, for example here.


Is greedy algorithm the best algorithm for set cover problem? Theorem: Unless $NP \subset DTIME (n^{O(\log \log n)})$, there is no $(1-o(1))\ln n$-approximation for set cover problem.

I am a bit confused by this theorem. As we know, greedy algorithm is $(\ln n+1)$-approximation, does this mean greedy algorithm is almost the best algorithm for set cover problem?

In the wiki set cover problem, there is a very bad example about the greedy algorithm, so I think a $\ln n$-approximation is meaningless. Does the theorem above say that it is impossible to design a constant approximation algorithm?

The result you quote, due to Feige, has actually recently been improved by Dinur and Steurer (based on earlier work of Moshkovitz), who showed that unless $P = NP$, there is no polynomial time $(1 - o(1))\ln n$-approximation algorithm for set cover.

This result states that if all you care about is the worst case approximation ratio, then you cannot substantially improve on the trivial greedy algorithm. (There are also other algorithms achieving the same $\ln n$ bound.) In particular, no polynomial time algorithm gives a constant factor approximation for set cover on all instances.


Why does arithmetic left shift of negative number leads to positive number? According to this Wikipedia article, when arithmetic left shift operation is applied to a signed number, the number is multiplied by 2. But there are certain situations where a negative number becomes a positive number when an arithmetic left shift is applied.

Eg.: Take a 2's complement signed integer -5 and 5 bits are used to represent it.

11011 ==> -5
10110 ==> -10 (-5x2)
01100 ==> +12 (?)

So after two arithmetic left shifts -5 became 24. I expected -20. Why is this the case?

$01100 \Rightarrow +12$, not $+24$.

And it is $+12$ because $32-20=12$. With $5$ bits and $2$s complement you can only represent numbers in the range $-16$ to $+15$. You have overflowed this range and, in effect, "run around" to the other end and into the positive number range.


Intersection of two NPDAs Is there a way to take the interection of two NPDAs?

I can't seem to find anything that can make that happen, but it seems like the type of thing that is should be relatively trival.

The intersection of two context-free languages can be non-context-free. The classical example is
$$ \{ a^n b^n c^m : n,m \geq 0 \} \cap \{ a^m b^n c^n : n,m \geq 0 \} = \{ a^n b^n c^n : n \geq 0 \}. $$
So in general you cannot simulate the intersection of two NPDAs with an NPDA.


NFA string acceptance with loop of epsilon transitions I am writing an algorithm to test whether a NFA accepts or not a string, and there is a case in which I don't know how the algorithm should behave namely:

How should the algorithm behave? Should it stop and understand that no string is accepted or should it run for infinite time?

An algorithm for testing whether an NFA accepts a string has the following specification:

Input: NFA $A$ and word $w$
Output: Yes if $A$ accepts $w$, No if $A$ doesn't accept $w$

In particular, the algorithm must always terminate. What algorithm you use is up to you.

One way to overcome the problem of $\epsilon$-loops is to compute, for each prefix of $w$, the set of states that the NFA can reach. To this end, for every state $q$ we define $N_\epsilon(q)$ as the set of states reachable from $q$ via (possibly zero) $\epsilon$-transitions. You can compute $N_\epsilon(q)$ using a graph traversal algorithm such as BFS/DFS.

Given a word $w = \sigma_1\ldots \sigma_n$, we define the set of states $R_i$ reachable after reading the first $i$ letters as follows:

$R_0 = N_\epsilon(q_0)$.
For $i = 1,\ldots,n$, $R_i$ is the union of $N_\epsilon(q')$ for all $q' \in \delta(q,\sigma_i)$ and all $q \in R_{i-1}$.

The NFA accepts $w$ iff $R_n \cap F \neq \emptyset$, that is, if $R_n$ contains an accepting state.

In your example, $N_\epsilon(1) = N_\epsilon(2) = \{1,2\}$. The fact that the graph induced by the $\epsilon$-transitions contains directed cycles is not problematic at all for this approach, since we only care about which states are reachable from which.


Prove that the next multiple of 4 is obtained using the next formula I was reading an assembly procedure that needed to align addresses on 4 bytes boundary for performance reasons so it has used the next statement that i formulated as a theorem to be proven.

Let $s$ be an integer that is not a multiple of 4 ($s \% 4 \neq 0$). $m$, the first next multiple of 4 such that $m \gt s$ is obtained using the following formula, where the operands are expressed in base 2 (Binary): $m = s + (\lnot s \land 11)$ ($\lnot a$ will return the 2's complement of $a$).

How to prove that ?

Suppose that $s = 4a+b$, where $0 \leq b < 4$; by assumption, $b \neq 0$. If the numbers are $n$ bit long, then $\lnot s = 2^n - s = 4(2^{n-2}-a) + (4-b)$. Since $b \neq 0$, the last two bits of $\lnot s$ will be $4-b \in \{1,2,3\}$. Therefore $(\lnot s) \land (11)_2 = 4-b$. Adding this to $s$, we get $4a+b+4-b = 4(a+1)$.


Can there be a context free language that is not recognizable by a PEG? This is related to this question. Essentially, I want to know whether my reasoning is correct.

We know that parsing with a context free grammar is same as boolean matrix multiplication (forward: Valient 1975, backward: Lee et al. 2002), and the latter has a lower bound of O(n^2) for arbitrary matrices.
If so, then there should exist a context free language $L$ such that any context
free grammar that can represent it would take $O(n^2)$ for matching a string.
This is because say there existed a grammar $G_n$ that allowed matches
faster than $O(n^2)$ for any given CFL, then that grammar would allow faster multiplication for
the corresponding Boolean matrices. Since Valient et al. and Lee et al.
together shows that multiplication of BMs are same as parsing with a CFG, any
BM can then be multiplied faster than $O(n^2)$, which is lower than the lower
bound by theory.

So there should exist a context free language $L$ such that it takes at least O(n^2) time for checking membership in $L$.

PEGs are known to require only linear time (Birman and Ullman 1970), (Loff et al. 2019).

If there exist a PEG for $L$, it would be a recognizer that checks the membership in linear time, and hence, can solve matrix multiplication in linear time.

Hence, there does not exist a PEG for $L$.
Where am I going wrong?
Valient 1975

context-free recognition, for $n$ character input strings, can be
carried out at  least as fast as multiplication for $n \times n$ Boolean
matrices

Lee et al. 2002

Any CFG parser with time complexity $O(gn^{3-\epsilon})$, where $g$ isthe size of the
grammar and $n$ is the length of the input string, can be efficiently
converted into an algorithm to multiply $m\times m$ Boolean matrices in
time $O(m^{3-\epsilon/3})$.

Loff et al. 2019

In fact, the only method we know to prove that a language has no PEG is
by using the time-hierarchy theorem of complexity theory:
using diagonalisation one may construct some language $L_2$ which is
decidable,say, in time $n^2$ (by a random-access machine), but not in
linear time, and because PEGs can be recognised in linear time using
the tabular parsing algorithm of Birman and Ullman [2] (or packrat
parsing [32,33]), there will be no parsing expression grammar for $L_2$.

I see two flaws in this proof sketch, one related to CFLs vs CFGs, and another related to nested quantifiers and running time as a function of multiple parameters.

Any time you have a high-level proof strategy that seems to lead to surprising results, it is a good idea to check it carefully by expanding each step to obtain a detailed proof.  Expand each claim with a precise statement, by applying the definition or the exact theorem in the literature, and verify carefully that they match up.  This is particularly important when dealing with lower bounds, as they tend to introduce nested quantifiers that can lead your intuition astray when thinking only at a high level.

Flaw #1: CFLs vs CFGs

The proof seems to conflate context-free languages (CFLs) with context-free grammars (CFGs).  However, there can be multiple CFGs that all generate the same CFL.  At best, your proof strategy shows that there exists a CFG $G$ that can't be parsed by a PEG parser.  But that's not surprising; we already know that PEG parsers can only parse CFGs that are in the PEG format.  We cannot  conclude anything about the corresponding CFL $L(G)$; for all we know, there might exist some other grammar $G'$ that is a PEG grammar and that yields the same language, i.e., $L(G)=L(G')$.  Your proof doesn't rule that out, so it does not prove that the CFL it constructs can't be parsed by a PEG parser.

A concrete example of this is given at https://en.wikipedia.org/wiki/Parsing_expression_grammar#Expressive_power, which shows a simple CFG that cannot be parsed by a PEG parser, but where there exists another CFG for the same language that can be parsed by a PEG parser.

Flaw #2: Multiple parameters

It's important to expand out the statement of what is meant by these lower bounds.  The lower bound on matrix multiplication means that, for each matrix multiplication algorithm, there exists an infinite family $(A_1,B_1),(A_2,B_2),\cdots$ of matrices such that $A_n,B_n$ are $n\times n$ matrices, and multiplying $A_n \times B_n$ using this algorithm takes $\Omega(n^2)$ time.

Lee's reduction describes how to construct a matrix multiplication algorithm from any context-free parser.  If we now apply Lee's reduction to the matrix multiplication algorithm obtained from a PEG parser, we obtain an infinite family $(G_1,w_1),(G_2,w_2),\cdots$ of CFGs and inputs such that parsing them takes a long time.  You'll need to dive into the details of Lee's reduction to determine the sizes of the $G_n,w_n$.  Based on a quick look, it looks to me like the size of $G_n$ is $\Theta(n^2)$ and the size of $w_n$ is $\Theta(n^{1/3})$, but I'm not sure whether that's correct; you'd need to figure that out.

Next, you'd need to figure out the running time of a PEG parser, as a function of both the size $g$ of the grammar and the size $n$ of the input string.  Standard references state the running time of a packrat parser for a PEG grammar as $O(n)$, but they don't describe the dependence on $g$; is it $O(gn)$? $O(g^2n)$? something else?  You'd need to figure that out, and then apply it to the family above, to determine what the asymptotic running time of this parser is on the family $L_n,w_n$, and thus what the running time of this matrix multiplication algorithm is on the family $A_n,B_n$, to determine whether it contradicts the $\Omega(n^2)$ lower bound.

For instance, if the running time of a PEG parser is $O(gn)$, then Lee's reduction yields a matrix multiplication algorithm that takes $O(n^{2.333\ldots})$ time on the family $A_n,B_n$, which does not contradict the known lower bound.

Notice how Lee's result does not provide a single context-free grammar or context-free language where parsing is slow; it provides an infinite family of pairs of languages and inputs (which was not considered in your proof strategy).  Also note the importance of getting the nested quantifiers right, and of capturing how the running time of a parser depends on both the size of the input and on the size of the grammar (which was not considered in your proof strategy).  Hopefully this highlights how a strategy that sounds good can run into difficulties when one tries to apply it in detail; and one must check those details before assuming the strategy will work out.


Minimum vertex cover algorithm with linear programming Consider the following algorithm: given a graph $G$ with $n$ vertices, set up a linear programming problem LP where there is a variable $x_i$ for each vertex $v_i$ of $G$, each variable can take value $\geq 0$, for each edge $v_av_b$ of $G$ set the constraint $x_a+x_b\geq 1$. The objective function is $\min\sum\limits_{1}^{n}{x_i}$.
Find the variable (or one of the variables) $x_i$, among the variables not set to $0$, that set to $0$ gives the minimum value of the objective function. Add the constraint $x_i=0$ to LP. Repeat until the optimal solution of LP is integer (that is each variable takes value in $\left\{0; 1\right\}$).
I am looking for a graph where the vertices associated to the variables that take value $1$ in the final optimal solution of LP are not a minimum vertex cover of $G$ (if it exists).

Consider the graph
  2-4---7
 /  |\ /|
1   | × |
 \  |/ \|
  3-5---6

Setting $x_1,x_2,x_3,x_6$ or $x_7$ to 0 gives your LP a value of 4, while setting $x_4$ or $x_5$ to 0 gives your LP a value of 5. However, if you set $x_1=0$, you will finally get a vertex cover of size 5, while the optimal vertex cover is of size 4.


Proof that there is unambigous grammar for every regular language How can I prove, or where can I find proof that for every regular language there is unambigous grammar?

Something like this might work. First, note that every regular language is accepted by some minimal DFA. Call such a DFA $M$. Next, describe how you could construct a right-regular grammar that accepts the same language as $M$. Take as your set of nonterminal symbols the set $Q$ of states of $M$. Form the set of productions as follows: the smallest set of productions such that if $M$ has a transition from $q_1$ to $q_2$ on $\sigma$,  then there is a production $q_1 \rightarrow \sigma q_2$, and also a production $q_1 \rightarrow \sigma$ if $q_2$ is an accepting state. (You'll also need to add the production $q_0 \rightarrow \epsilon$ if the empty string is in the language).

Now, if this grammar is ambiguous, there are two different derivations for some string. This would imply that, at some point, more than one transition was available in the minimal DFA (since each production corresponds to some transition). This is a contradiction, since there cannot be more than one valid transition at any time while a DFA processes input.

Basically, while you're very right that right-regular grammars can be ambiguous, you can actually construct a specific right-regular grammar that must be unambiguous. All you have to do is describe the method of construction and produce a valid argument why it's right-regular and why it can't be ambiguous.


Real world applications for Steiner Tree Problem? Are there real-world applications of the Steiner Tree Problem (STP)?

I understand that VSLI chip design is a good application of the STP.  Are there any other examples of real world problems that people can suggest of that could be formulated in terms of the STP?

Background: I am beginning my PhD research and I am looking at using hybrid metaheuristics and primal-dual methods for the decomposition and solution of large-scale combinatorial optimisation problems.  I find the STP fascinating, and I'm wondering if there is much real-world motivation for studying it, or if it is primarily of theoretical interest.

I am currently writing my PhD proposal, which is about finding ways to apply theory from parameterized complexity, primarily tree decompositions, to realistic network optimization problems. But I mainly plan to work with Steiner Tree, not in the last place because its simple and there are a lot of papers/benchmarks available.

Stumbled on this question because I too have some trouble finding practical motivations for studying it. I think its practical relevance is more easily motivated by the enormous amount of optimization problems that are generalizations of the vanilla STP but are more flexible. There is a nice list here: http://theory.cs.uni-bonn.de/info5/steinerkompendium/netcompendium.pdf

I think some of the problems mentioned with phylogenetic trees can be directly formulated as STP but I haven't read the papers thoroughly.

This algorithm for connected facility location and single source rent-or-buy is also interesting: http://sma.epfl.ch/~eisenbra/Publications/jcss08cfl_final.pdf
Though not directly modeled as an STP, solutions to these problems have a core that is a Steiner Tree and the algorithm makes use of a STP approximation algo directly to solve that part.

Also regarding heuristics for the STP you might be interested in this page: http://dimacs11.cs.princeton.edu/workshop.html
There are quite a few new competitive algorithms that have been presented there.

Edit: You might also want to take a look at this book by William Cook:

In Pursuit of the Traveling Salesman

It is about the TSP, but that one is similarly theoretical. Chapter 3 contains really a load of concrete practical uses, not just the trivial tour finding stuff, but unexpected problems that can be solved by solving a TSP, including some biology problems as I mentioned. Part of the reason of the applicability seems to be the fact that there is a very powerful and accessible TSP solver out there, making it convenient to rephrase design problems as TSP's. I found it really inspiring as the same type of applications could be found for the STP I think (but there is no 'industry standard' solver for it so it doesn't happen in reality).  Some of the chapter is free on Google books, though I recommend getting you hands on the full version cause some of the best examples are left out.


Does big-Oh notation in optimization follow the same convention as in CS? I first learned big-Oh (little-Oh, big-Theta.....) complexity for growth of functions using CLRS in a computer science class.
Now I am doing a project on optimization. In our optimization class, we were introduced to the notion of rate of convergence which are characterized by the ratio:
$\lim\limits_{k \to \infty} \dfrac{|x_{k+1} - L|}{|x_k-L|}$
where $L$ is the limit of the sequence $(x_k)$. And from there we define linear, superlinear and sublinear convergence raes.
However, when I looked up on some reference online, the above notions of rate of convergence is almost never used. Instead, all the convergence rates are characterized in terms of big-Oh. Quoting from the slides:

Theorem: Gradient decent with fixed step size $t\le\frac{1}{L}$ satisfies $f(x^{(k)})-f(x^*)\le\frac{\|x^{(0)}-x^*\|^2}{2tk}$.
I.e. gradient decent has convergence rate $O\left(\frac{1}{k}\right)$.
I.e. to get $f(x^{(k)})-f(x^*)\le\epsilon$, we need $O\left(\frac{1}{k}\right)$ iterations.

Unfortunately, these authors never define what their notations mean. I am in need of citing the definitions of big-Oh for my class project.
Is there any disparity between the rate of convergence in terms of big-Oh (and other asymptotic) used in optimization versus that used in CS (as can be found in a standard textbook such as CLRS)?
Is there an optimization textbook that addresses big-Oh notation?

They are using the standard Landau notation.

In the theorem you stated, it is said that after $k$ steps your distance from the optimal value is smaller than $\frac{c}{k}$, where $c$ is a constant which depends on your initial distance from the point where optimum is achieved, and on the step size. In that case you can indeed say that the convergence rate is $O\left(\frac{1}{k}\right)$, which is interpreted as you quoted in the following line, to get $\epsilon$-close to the optimal value one needs $O\left(\frac{1}{\epsilon}\right)$ iterations.

Note that I wouldn't take this answer as "anywhere in optimization this notation means the Landau notation", and you are probably right to say that it needs to be mentioned. However, in this context, you can pretty safely assume that this was the authors intention.


Is it possible to interpret some Martin-Löf types as abelian monoids in such a way that any abelian monoid can be represented as a type? For instance, I can interpret the unit type as the trivial monoid with one element. Non-dependent pairs $A \times B$ can be interpreted as the direct sum $A ⊕ B$ when $A$ and $B$ can both be interpreted as abelian monoids. For the sum type $A + B$, you can define the monoid operation as:
$$inj_L(a_0) \cdot inj_L(a_1) = inj_L(a_0 \cdot a_1)$$
$$inj_L(a) \cdot inj_R(b) = inj_R(b)$$
$$inj_R(b) \cdot inj_L(a) = inj_R(b)$$
$$inj_R(b_0) \cdot inj_R(b_1) = inj_R(b_0 \cdot b_1)$$
(Although this does mean that the interpretations of $A+B$ and $B+A$ are different).

So far though this scheme only lets me represent finite monoids where $\forall x: G, x \cdot x = x$. I'd like a way to extend it to infinite and more interesting monoids. That will at least require a way to interpret W-types but I can't see what that interpretation could be. Does such an interpretation exist? Or is there a simple proof that what I'm trying to do is impossible?

Fortunately you gave us some context in the comments (always a good idea to include it in your question). Rather than doing what you're trying to do, I believe quantitative type theory is what you're looking for.


Is there a term for a tree where the values of the children add up to a fixed value? I have a tree with percentages of the following form

        100
       /   \
      /     \
     /       \
    /         \
   25          75
  /  \       / | \
 15  10    35  10 30
    /  \      / \
   1    9    5   5
      / | \
     3  3  3

So child nodes are added up in the parent node.

Does a tree with this attribute has a already defined name in the algorithmic world?

Thanks for the positive feedback so far.

In this case the nodes hold actually values which are added up in the parent and the example tree shows the percentages of these values in comparison to the root.

I have to implement an algorithm to find those nodes which have the biggest impact and add up to 95 percent.

Since the problem description in case what "biggest impact" means, is pretty open I was thinking about setting the percentage in relation to its child nodes + itself.

Therefore node 25 would have a weight of 25/8, node 75 would have on of 75/6 and so on.

In the next step I would order by weight, min amount of children, in descending order and add up the percentages of the nodes until I reach 95 percent. Always removing a sub node from the result when the parent is added.

I hope I could make myself clear

I believe it is creatively called a "sum tree."

Algorithmically it's not especially useful nor interesting because it is not efficiently modifiable.


Algorithm for detection of overlaping between vectors I am currently developing a math-physics program and I need to calculate if two vectors overlap one another, the one is vertical and the other is horizontral. Is there any fast algorithm to do this because what I came up so far, has a lot of repeats. Eg lets say we have vector V1((0,1),(2,1)) and a V2((1,0),(1,2)) where the first parenthesis is the coordinates starting and the second coordinates that the vector reaches. I want as a result to take that they overlap at (1,1)

So far the only idea I came up is to ''expand'' each vector to a list of points and then compare the lists e.g for V1 its list would be (0,1) (1,1) (2,1)

If you have two line segments and you want to know if they intersect, see https://en.wikipedia.org/wiki/Line_intersection and https://en.wikipedia.org/wiki/Line_segment_intersection.

For next time, I'd expect you to do more research on your own.  See especially "computational geometry", e.g., a textbook that covers that area.


Determine minimum and maximum number of leaves on a complete tree I want to determine the minimum and maximum number of leaves of a complete tree(not necessarily a binary tree) of height $h$.
I already know how to find minimum($h+1$) and maximum($2^{h+1}-1$) number of nodes from the height, but what about leaves? Is there a way to determine them knowing nothing but height of the tree?

Hint:

   Try the case $h=1$.  What's the minimum?  What's the maximum?


Is it decidable whether a Turing machine will ever leave the start state on any input? Is $L=\{ M | M\text{ leaves the start state on every input}\}$ decidable?

I have an intuition that the following language is undecidable, since the complement $L^C$ seems to not be recursively enumerable. Some TM might remain on the start state for $k$ steps, but then leave at $k+1$ steps, so we can't get a definitive answer whether it will ever leave the start state.

What known non-decidable TM can be reduced to A to show that a contradiction arises?

I would say decidable. Here is the idea.

Firstly, let your alphabet be $\Sigma$, including the empty symbol. I claim that unless you have in the transition function $(s_0, x) \to (s_i, \dots)$ for every $x \in \Sigma$ and $ i \neq 0$ your machine is not the desired one. Why this is true?
Suppose there is such $x$ for which TM doesn't change the initial state. Fill the tape with all these $x$'s. Done.

Here I had the assumption that we can have any initial tape as we want. If you consider only finite non empty input the problem becomes much harder.


Doing beta reduction while constructing the boolean expression in lambda calculus I am going through beta reduction in lambda calculus . And beta reduction to my understanding is an act of  substitution  like in the following :

$ (\lambda x.P) M $ is said to be beta reduced to : $ [M/x]P $

So then my course was led to encoding the Booleans in lambda calculus . And the following two expressions were used to encode the true and false boolean expressions :

$ \lambda xy.x$ for true denoted by T

and $ \lambda xy.y$ for false denoted by F

The basic idea behind constructing these expressions is to find expressions that
 analogically mimic the "and" operation if the "application" is the couterpart of "and"

So , for the above two expressions the book says $TT = T $ ,$ FF = F $, $TF= F $ , $FT=F $.

I tried to  do the beta reduction for ($ \lambda xy.x$ )($ \lambda xy.x$ ), which means [ $ \lambda xy.x$ /$x$]$ \lambda xy.x$ .

I could break $ \lambda xy.x$  as $\lambda x . \lambda y.xy  $ but I am unable to find how to use this to advantage to get  the final reduction .

How to carry on the reduction from here so as to prove that ($ \lambda xy.x$ )($ \lambda xy.x$ ) = $ \lambda xy.x$  ?

It is helpful to look at $\lambda$ abstractions as functions, e.g. $T \equiv \lambda x y. x$ "is" a function that takes $2$ variables as arguments ($x,y$; those between "$\lambda$" and ".") and returns the first of them - $x$ (expression after the "."). On the other hand, we define $F$ to also take $2$ arguments and return the second one - $y$.

In this sense, $\beta$-reduction is a process of evaluating a function at given values (the ones that abstraction is applied to). One should be careful about $\alpha$-renaming and have in mind currying, but we will not go into that here.

Let's now define the $AND$ operator.

What does it take as arguments?
We can also think of it as a function, and therefore it must take $2$ arguments (truth values), so we would define it something like
\begin{equation}
AND := \lambda a b.\ <body,\ i.e. what\ it\ returns>.
\end{equation}

What does it need to return?
If it receives $T$ and $T$ for it's arguments, it must return $T$. Otherwise, it returns $F$.

Constructing the body.
Having in mind that $a$ and $b$ will be substituted with $T$ or $F$, we can use them in the body of $AND$. We will use their property of returning the first or second argument. Consider the following definition;
\begin{equation}
AND := \lambda a b.\ a\ b\ F
\end{equation}
Upon receiving its arguments $a$ and $b$, operator $AND$ is returning the application of its first argument (and we know it will be a "function" of $2$ arguments that returns either its first or the second argument) onto its second argument and $F$. Therefore, if the first argument ($a$) happens to be $T$, we return the second argument ($b$) as a solution (in other words, the result of $AND\ T\ b$ is $b$). If the first argument ($a$) happens to be $F$, we return $F$.

Cases. There are $4$ cases that can happen.

$AND\ F\ F$. This will evaluate as follows:
\begin{equation}
(\lambda a b.\ a\ b\ F)\ F\ F = F\ F\ F = (\lambda x y.\ y)\ F\ F = F
\end{equation}
$AND\ F\ T$. This will evaluate as follows:
\begin{equation}
(\lambda a b.\ a\ b\ F)\ F\ T = F\ T\ F = (\lambda x y.\ y)\ T\ F = F
\end{equation}
$AND\ T\ F$. This will evaluate as follows:
\begin{equation}
(\lambda a b.\ a\ b\ F)\ T\ F = T\ F\ F = (\lambda x y.\ x)\ F\ F = F
\end{equation}
$AND\ T\ T$. This will evaluate as follows:
\begin{equation}
(\lambda a b.\ a\ b\ F)\ T\ T = T\ T\ F = (\lambda x y.\ x)\ T\ F = T
\end{equation}

This is a somewhat friendly $\lambda$-calculus workflow I presented here, but I think it is the right approach for someone who is starting to learn about it and needs some intuitive notes on its nature.

For further research, following links should be useful as a starting point;

definitions of logical operators: https://en.wikipedia.org/wiki/Church_encoding#Church_Booleans
$\lambda$-calculus interpreter to try out your ideas and see reduction steps; http://jacksongl.github.io/files/demo/lambda/index.htm


Covering radius of code Let $C$ be a  $[n, k]$ linear code over $\mathbb{F}_q$.

I want to calculate the covering radius of the Hamming codes.

I have thought the following:

Since the Hamming distance is $3$, the coverig radius will always be $3$.

Am I right?

The Hamming codes are perfect codes. This means that balls of radius $(d-1)/2$ (where $d$ is the minimal distance) centered around the codewords partition the space. In particular, the covering radius is $(d-1)/2$.


Can a $k$-ary relation have polymorphisms of arity greater than $k$? To quote Hubie Chen's A Rendezvous of Logic, Complexity, and Algebra (2009) on constraint satisfaction and complexity,

  An operation $f : D^m \to D$ is a polymorphism of a relation $R \subseteq D^k$
  if, for any choice of $m$ tuples $(t_{11}, ... , t_{1k}), ... , (t_{m1}, ... , t_{mk})$ from $R$, it holds that the tuple obtained from these $m$ tuples by applying $f$ coordinate-wise, $( f (t_{11}, ... , t_{m1}), ... , f (t_{1k}, ... , t_{mk}))$, is in $R$.

Two examples follow, but neither answers this question.  Let's say that there's a relation $R$ and function $f$ such that $m > k$.  Is $f$ a polymorphism of $R$?

Concrete example: Assuming an $\wedge$ relation $\{ (1,1) \}$ (i.e. arity is 2), is the majority function $f(a,b,c) = (a \wedge b) \vee (a \wedge c) \vee (b \wedge c)$ a polymorphism of this relation?

Let's say that there's a [$k$-ary] relation $R$ and [$m$-ary] function $f$ such that $m>k$. Is $f$ a polymorphism of $R$?

Maybe, maybe not: it depends on the function and the relation.  A given $k$-ary relation may have polymorphisms of arity arity less than, equal to, and/or greater than $k$. In fact, every relation has polymorphisms of all arities. For example, the ($1$-ary) identity function is a polymorphism of every relation, as are the projection functions $f_\ell(x_1, \dots, x_m) = x_\ell$ for all $1\leq \ell\leq m$. (Exercise: check these examples.) Notice that the identity function is just the case $\ell=m=1$.

  Concrete example: Assuming an $\wedge$ relation $\{ (1,1) \}$ (i.e. arity is 2), is the majority function $f(a,b,c) = (a \wedge b) \vee (a \wedge c) \vee (b \wedge c)$ a polymorphism of this relation?

Check the definition! $f$ is a polymorphism of $R_\land = \{(1,1)\}$ if, and only if, for all $(x_1,x_2),(y_1,y_2),(z_1,z_2)\in R_\land$, we have $(f(x_1,y_1,z_1),f(x_2,y_2,z_2))\in R_\land$. Well, the only tuple in $R_\land$ is $(1,1)$, so we only care about the case $x_1=y_1=z_1=x_2=y_2=z_2=1$. And we see that $f(1,1,1)=1$, so $(f(1,1,1),f(1,1,1))\in R_\land$, so $f$ is, indeed, a polymorphism of $R_\land$. Further, by exactly the same argument, any function such that $f(1, \dots, 1) = 1$ is a polymorphism of $R_\land$.

The polymorphism property is often represented as a table: given a $k$-ary relation $R$ and an $m$-ary function $f$, we can write

$$\begin{matrix}
    (t_{1,1} & t_{1,2} & \cdots & t_{1,k}) & \in R\\
    (t_{2,1} & t_{2,2} & \cdots & t_{2,k}) & \in R\\
    \vdots   & \vdots  & \ddots & \vdots   & \\
    (t_{m,1} & t_{m,2} & \cdots & t_{m,k}) & \in R\\
\hline
    (f(t_{1,1}, \dots, t_{m,1}) & f(t_{1,2}, \dots, t_{m,2}) &\cdots & f(t_{1,k}, \dots, t_{m,k})) &\in R
\end{matrix}$$

The meaning is that we require that, whenever the tuples above the line are in $R$, the tuple below the line must also be in $R$.  Notice that nothing in the structure of the table requires any relation between $k$ and $m$: the property could hold (or not hold) for a relation of any arity and a function of any arity.  It's just required that, whenever we write a collection of tuples in $R$ and "apply $f$ to each column", the resulting tuple is always still in $R$.


What does starvation freedom exactly mean? Galvin offers the following definitions of starvation:

Indefinite blocking, or starvation, a situation in which processes wait indefinitely within the semaphore.

A major problem with priority scheduling algorithms is indefinite block-ing, or starvation.A process that is ready to run but waiting for the CPU can be considered blocked. A priority scheduling algorithm can leave some low priority processes waiting indefinitely.

What I understand from this is, starvation happens whenever a process has to wait indefinitely to get resources, the waiting may be finite, but you cannot specify the time limit. So by definition, starvation freedom must be definite waiting.
Michel Raynal defines starvation freedom as following:
If a process wants to execute the critical section code, then that process eventually executes it.
My question is, does starvation freedom mean a given process will have to wait for a specified finite time(definite waiting, according to Galvin) or does it mean that a process must wait for some unknown finite time(eventually executes it, according to Raynal).

You cannot imply starvation freedom as definite waiting just because the definition of starvation says that the low priority processes have to wait indefinitely.
From Raynal,

Starvation freedom means that a process that wants to enter the critical section can be bypassed an arbitrary but finite number of times by each other process.

Concurrent Programming: Algorithms, Principles, and Foundations
By Michel Raynal