How to detect number of specific object in an image and it's diameter(size)?

Well to answer your last question, you cannot train with the images that you want to test your algorithm with, that is a paradox...

You will need more than just two images if you want to build a robust model that can detect each rod AND predict their diameter. Those are two different problems, and you might want to split your model in two branches: one to detect each rod, the other to predict its diameter as a regression problem.

If you can obtain a larger dataset with ground truth, then you can proceed to train your model. I would tend to say that using an object detector CNN would be overkill, but if you need to predict the diameter of each rod in the image, it might be necessary. So maybe look into TinyYOLO for the detection part, and then you could use the predict bounding box of each rod in the image for a small perceptron to infer the diameter.


Why does the Θ-class survive adding a constant only for positive, monotonic, and non-decreasing functions?

Let $f(n) = 1-1/n$ and $g(n) = 1/n$, so we've violated the condition that $g$ is non-decreasing. However, it's not hard to show that $f(n) \in O(g(n)+2)$ but we also have $f(n)\notin O(g(n)$, invalidating the inference.


Count of distinct substrings in string inside range

The question does not motivate the number of queries being $O(n)$, which seems an arbitrary worst case since the number of unique possible queries is the number of ordered pairs and thus $O(n^2)$.

Here are two different solutions with better time complexity for the $O(n^2)$ case based on (implicit) suffix trees constructed incrementally with Ukkonen's algorithm. Both solutions are based on preprocessing and have complexity $O(n^2 + |Q|)$ where $Q$ is the set of queries. The second solution runs in $O(n + |Q|)$ if all queries have the same width.

Solution 1 - Preprocess all unique queries

Iterate over the suffixes of $S$. For each suffix $S_i=S[i..n]$, build the suffix tree of $S_i$ with Ukkonen's algorithm. After update $j$ to the current suffix tree, store the tree size in a matrix at position $(i,i+j-1)$. A query for the range $[x,y]$ is answered by the matrix element at $(x,y)$.

Suffix tree size can be stored along with the suffix tree and updated in constant time at each step by modifying the update procedure in Ukkonen's algorithm. For each update the size increases by the current number of leaves.

Solution 2 - Preprocess unique query widths

This solution is harder to implement but requires less preprocessing work if there are few query widths. Preprocessing takes $O(n)$ time if there is only one query width.

For each query width $w$, use a sliding window of width $w$ and incrementally build a suffix tree. Remove the suffix starting one character to the left of the window by remove the longest suffix from the tree. At each step, the current number of substrings within the sliding window is the tree size.

All queries can then be answered in linear time by using the results of the precomputation.

Note: removing the longest suffix can be done by removing the oldest leaf of the suffix tree. It is not easy to implement correctly.


I suggest you try a simple solution: randomly decide whether to assign users to an experiment when they visit the corresponding page.

Suppose you want to have 100 users to a particular experiment, call it experiment E.  When a user visits the page for experiment E, if that user hasn't been previously assigned to any experiment, flip a biased coin and assign the user to experiment E if that coin comes up heads.  How do you decide what the probability of heads should be?  If historically you see 2000 visitors per two-week period, and you want 100 users, then the heads probability should be about 1/20.  Then after two weeks you should get about the desired number of users.

This assumes you have historical data on the number of visitors to each page, to set the probability appropriately.  If you don't have historical data, there are some alternative strategies you could use.  For instance, if you want 100 users for experiment E, you could randomly pick 100 different times throughout the two-week period; for each selected time, take the next unassigned user who visits that page (the first one who visits the page after that time) and assign them to experiment E.  In this way you are randomly selecting 100 different users.

These techniques treat each experiment independently, which simplifies the assignment process.  This is simple and I suspect it might work well enough for running experiments in practice.  Only consider something more complicated if you have evidence that this won't work.  (How can you tell whether it will work?  You could take your historical data and simulate the strategy on historical data and see if it gets you enough users for each experiment.)


Minimize Deterministic Finite Automata with no accepting states

A finite automaton without end states denotes the language L = $ \emptyset $ . To minimize a DFA we minimize the number of states and the denoted language must be the same. By definition of DFA we must have an initial state $ q_0$ so $| Q | \geq  1$ and as you say we need to include the transition function with all transition into $ q_0 $ (because creating dead states is counterproductive).


Sampling in large graph using simple random walk

While the algorithm doesn't know the graph, when you are analyzing the performance of the algorithm on a graph, you do know the graph.

For a similar example, take the egg dropping puzzle. In this puzzle, the algorithm doesn't know the value of $T$, but when analyzing the algorithm, you are allowed to use the value of $T$; indeed, otherwise it's not clear how you'd ever end up with a running time depending on $T$.


OS: Why is it necessary to have hardware support for implementing Preemptive Scheduling Strategies?

A preemptive scheduler must stop a program that is looping and not calling any operating system function. The program is not triggering any fault as division by zero.
We are assuming that the interrupt are enabled and assuming single core processor.
Only a timer interrupt can succeed to regain control of the processor.
The rate set by this timer gives you the maximum switching time for the scheduler.
The preferred value is 1000 Hz which gives 1 ms resolution.
For computers not fast enough to allow so many timer interrupt per second, the next popular values were:
60 Hz, from the video card refresh rate
18 Hz, from a 16 bit overflow of IBM PC original timer chips ; color TV cristal of 3.59 MHz / 3 / 65536
Other option: cooperative multitasking. This is how apollo computer managed to run many tasks... As well as Windows 3.1
You call a lightweight scheduler everywhere your code perform long loops.
The lightweight scheduler usually just decrement an integer and immediately return if the value still not zero.
For the rare case where the integer reach zero, immediately set that integer to the default value and perform the next tests to decide if a new task with higher priority needs to be executed.
If a precise timing is needed, then at this point, reading a hardware timer counter and comparing the value with the previous one allow to evaluate precisely the elapsed time.


NP-hardness of problem with indices and subsets

This question shows that Vašek Chvátal is a hero.

Reduce from graph kernel.

In the GRAPH KERNEL problem, the input data is a digraph and the task is to determine whether it has a kernel.

A kernel of a digraph is a subset $S$ of its vertex set which satisfies (i) no two vertices of $S$ are adjacent, and (ii) for every vertex not in $S$ there exists an arc from some vertex in $S$ pointing to it.

So, we need to transform a digraph to your set matrix problem.

For each original vertex, create an element. Call these elements vertex-elements. Denote this set of element by $V$.

For each original arc, create an element. Call these elements arc-elements.

Now, to ensure $T$ is an independent set in this digraph. For each arc-element $a=(u,v)$, set $A[u,a]=V\setminus\{v\}$ and $A[v,a]=V\setminus\{u\}$. Also, just in case none of $u$ and $v$ is included in $T$, for every $w\neq u, v$, set $A[w,a]=V\setminus\{u,v\}$.

To ensure $T$ is a dominating set in a digraph, for each arc $a=(u,v)$ set $A[u,v]=V$

All the other entries of $A$ are set to $\emptyset$.


Why is this basic language not a regular language?

Every language is the union of regular languages:
$$
L = \bigcup_{x \in L} \{ x \}.
$$
However, the set of regular languages is not closed under infinite unions. It isn't even closed under countably infinite unions, as your example demonstrates.

You can prove that your language is not regular in many ways. For example, if your language were regular, then so would its intersection with $0^*1^*$ be; yet this language is $\{ 0^n 1^n : n \geq 0 \}$, the classical example of a non-regular language. You can also prove non-regularity of your language directly, using either the pumping lemma or Myhill–Nerode theory.


Clustering a set of images using keypoint descriptors

I don't know how to do it that way.  I would suggest you do it a different way:

Define a distance metric that measures the dissimilarity between two metrics.  In particular, if $I,J$ are two images, $d(I,J)$ should quantify how dissimilar $I,J$ are -- large values indicate they are very different, small values indicate they are very similar.
Use a different clustering algorithm that only needs a distance metric.

For #1, there are many ways of measuring/computing image similarity.  If you want to use SIFT as your starting point, you can align the two images and compute some metric based upon the number of keypoints that are well-matched ("inliers") vs the number that aren't ("outliers).

For #2, there are many options.  One option is to use hierarchical clustering.

I recommend you spend some time reading through the research literature on measuring image similarity in the computer vision literature.  There's lots of work, and many methods proposed and evaluated.

See also https://stackoverflow.com/q/843972/781723 and https://stackoverflow.com/q/4196453/781723.  You could also use the TinEye API.


NP-Hardness of Hamiltonian cycle with $|V|$ divisible by 3

There is no "purpose" for the condition that the number of vertices be divisible by 3 – it is part of the problem statement. DHAM3 is the special case of DHAM in which the number of vertices is divisible by 3. In principle this might make the problem easier (a special case can only be easier), but in this case DHAM3 is also NP-hard (and so NP-complete), as you can show by reduction from DHAM.

The problem SHAM3 is not a decision problem and so not eligible to be NP-complete or NP-hard.

How do you show that DHAM3 is NP-hard by reduction from DHAM? You have to come up with an efficiently computable function $f$ that takes an instance $x$ of DHAM and outputs an instance $f(x)$ of DHAM3 in such a way that $x \in DHAM$ iff $f(x) \in DHAM3$. In other words, $f$ takes a graph $G$ and outputs a graph $f(G)$ whose number of vertices is divisible by 3, and moreover $G$ is Hamiltonian iff $f(G)$ is Hamiltonian.

The difficulty here is that the original graph $G$ might have a number of vertices which is not divisible by 3 (otherwise you can take $f(G) = G$). I'll let you figure out how to overcome this difficulty.


Find all neighbors at a certain distance, in 3 dimensions

I recommend using a k-d tree or an octree to store the list of points.  They support efficient nearest neighbor search.

If you need to update the list, look at R-trees, which allow your list to be dynamic: you can add or delete from the list and efficiently update the R-tree data structure.


Can a CD disk and the memory of a device have an infinite space storage?

This is impossible.

Storing information requires physical space and there is a limit. This might seem somewhat obscured by the fact that we can store a lot of information in a small space, by the technological process which brought us smaller and smaller storage devices and by other factors which make the relationship between information and space less clear (e.g. a 700MB CD and a 50GB Blu-Ray disk have the same volume).

The limit on how much information can be stored is given by the Bekenstein bound:

$I \le \frac{2 \pi c R m}{\hbar ln2} $

$I$ is the information quantity that can be stored in a sphere with radius $R$ and mass $m$.

In short, you need an infinite amount of space to store an infinite amount of information, but a CD has a finite volume.


Let $w$ denote the weights of the neural network.  Define the objective function $\Psi$ by

$$\Psi(w) = \sum_i \left(\left(\sum_j NN_w(A_{ij},B_{ij},C_{ij})\right) - Q_i\right)^2.$$

Then, find $w$ that minimizes $\Psi(w)$ using gradient descent.  You can find the gradient of $\Psi(w)$ using backpropagation through the neural network.  You can use all the standard methods for speeding up training of neural networks: stochastic gradient descent, Adam or momentum or Adagrad, etc.

This is very similar to training neural networks for regression problems.  The only difference here is that you are summing the output of the neural network on multiple inputs.  It is straightforward to adjust the objective function to take that into account, as shown above.


I'm asked to draw DFA for this {$\epsilon$, 0} however I do not understand what {$\epsilon$, 0} mean

The problem is to find a DFA, such that the only two words it accepts are '$\epsilon$' - the empty word, and '0'


Efficient Algorithm to Find the n-th Odious Number

Here is the recursive formula for odious numbers,
$$\begin{align}
a_1&=1,\\
a_{2n} &= 6n-3 -a_n,\\
a_{2n+1} &= a_{n+1} + 2n.
\end{align}$$
The formula can be proved easily by observing, as greybeard pointed out, there is exactly one odious number among $2k-1, 2k$ for all positive integer $k$.
Here is a simple algorithm in Python to compute the $n$-th odious number.
def odious_number(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return 3 * (n - 1) - odious_number(n // 2)
    else:
        return odious_number((n + 1) // 2) + n - 1

if __name__ == "__main__":
    for i in range(1, 16):
        print(odious_number(i), end=", ")
    # Output: 1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28,

There is also a "closed" formula.
$$a_n = 2n - 1 - \text{hamming_weight}(n - 1)\ \%\ 2$$
So, we have the following one-liner.
def odious_number(n):
    return 2 * n - 1 - (n - 1).bit_count() % 2

 int.bit_count(), which returns the Hamming weight of an integer, is available since Python 3.10. Before that version of Python, we can use, for example, bin(i).count('1').


Grammar for parsing simple mathematical expression

Your grammar will generate mathematical expressions, but you haven't captured the notion of operator precedence. For instance, there are two different ways your grammar can generate the expression $a+a*a$, one having the interpretation we'd write as $a+[a*a]$ and the other having $[a+a]*a$. Using the jargon, we'd say your grammar is ambiguous.

A grammar that avoids this problem is

< expression > ::= < term > + < expression > | < term > - < expression > | < term >

< term > ::= < factor > * < term > | < factor > / < term > | < factor >

< factor > ::= (< expression >) | < float > | < var >

See if you can generate $a+a*a$ in two different ways using your grammar and then try the same thing with this grammar. That should give you an idea of what's going on here.


Decide if a specific Turing machine halts on a specific string

The problem you are referring to is sometimes known as the Acceptance problem. It is indeed undecidable.

Let me attempt to find the source of your confusion. I assume by linking the other thread you are referring to the following decidable language:

$$
L_{HP-M'-x} =
\begin{cases}
1 &  \text{M' halts on x} \\
0 &  \text{otherwise}
\end{cases}
$$

The reason this language is decidable is because, given any $M'$ and $x$, this language must be either $\{1\}$ or $\{0\}$. In particular, this MUST be a finite language, and ALL finite languages are decidable.

Note that this doesn't mean we can solve the Acceptance problem. Using classical logic, we deduce that either a machine accepts a string or it does not. The hard part is figuring out which case it is! We know that the language is decidable, but we do not know what a machine that accepts this language looks like because we don't know what the language itself looks like.


in O(n) time: Find greatest element in set where comparison is not transitive

The standard algorithm for finding a maximum still works. Start with $a_1$ and go over the elements, if you see a larger value, update the maximum to be that value. The reason this works is that every element you skipped is smaller than at least one element, and can thus not be the maximum.

To be clear, by the "standard algorithm" I mean the following:

max <- a_1
for i=2 to n
   if a_i > max
      max <- a_i
output max

For completeness, I will discuss here the issues raised in the comments. The setting in the above discussion is finding a maximum relative to an anti symmetric relation $<$, where $a_i$ is a maximum if for all $j\neq i$ we have $a_i>a_j$. The above algorithm works under the assumption that a maximum exists, however if this is not known, one can use it to verify the existence of a maximum (check whether the returned element is indeed greater than all other elements, this is mentioned in Chi's comment and in Ilmari Karonen answer).

If $<$ is not necessarily anti symmetric, then the above algorithm fails (as Emil mentioned in the comments). If $<$ is an arbitrary relation (i.e. we are relaxing both transitivity and anti symmetry), then it is not hard to show that finding a maximum in linear time is not possible. Denote by $\#a_i$ the number of times $a_i$ participated in a query, we define an adversarial relation in a way that the maximum cannot be revealed without enough queries. Given the query $a_i >?a_j $, answer $a_i>a_j$ if $\# a_i < n-1$ and $a_i<a_j$ otherwise. If the number of queries is $o(n^2)$, then a maximum was not yet seen, and it can be set to be either of the elements in the set.


Why is the running time of edit distance with memoization $O(mn)$?

I'm assuming $n,m$ are the lengths of the input strings. The number of sub-problems are the number of different inputs to the recursive procedure edit_distance, ignoring the memo input. You can check that s1 is always a suffix of the first input string and that s2 is always a suffix of the second input string. Since there are $n+1$ suffixes of the first input string and $m+1$ suffixes of the second input strings, the total number of sub-problems is $(n+1)(m+1) = O(nm)$.

If evaluating the body of edit_distance (minus the recursive calls) took $O(1)$, then the total running time would be $O(nm)$. However, this is actually not the case. The function make_pair and the ensuing hash take $\Theta(|s_1|+|s_2|)$, which for a majority of function calls is $\Theta(n+m)$. Therefore the running time is actually $\Theta(nm(n+m))$ rather than $\Theta(nm)$. This slowdown is avoided in the dynamic programming solution, which does run in time $O(nm)$.

($\Theta(\cdot)$ is similar to $O(\cdot)$; whereas $O(\cdot)$ is only an upper bound, $\Theta(\cdot)$ is both a lower bound and an upper bound. I need to use it here since the fact that the algorithm runs in time $O(nm(n+m))$ doesn't preclude the possibility that it actually runs in time $O(nm)$; to preclude this possibility we need a lower bound on the running time.)


Can two different complexity classes be equal relative to an oracle? Example request

Let $\mathsf{C}$ be a complexity class of your choice, let $\mathsf{O}$ be an oracle of your choice, and define $\mathsf{D} = \mathsf{C}^\mathsf{O}$. Then $\mathsf{C}^\mathsf{O} = \mathsf{D}^\mathsf{O}$, but it could happen that $\mathsf{C} \neq \mathsf{D}$. For example, you can take $\mathsf{C} = \mathsf{P}$ and $\mathsf{O} = \mathsf{HALT}$, the halting problem.

This might seem like cheating, but it's exactly the same answer as the one by Willard Zhan.


How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma?

This answer is a simpler version of Colin McQuillan's answer to the same question.

Suppose the language is regular. The pumping lemma gives strings $u,v,w$ such that every string $x_n=u v^n w$ is
a power of $2$.

Interpreting these strings as numbers and writing $d$ and $e$ for the lengths of $v$ and $w$ respectively, we have
$$
x_n = u 3^{dn+e} + v 3^{d(n-1)+e} + v 3^{d(n-2)+e} + \dots + v 3^e + w.$$
So,
$$x_{n+1}-3^dx_n = v3^e + w - 3^dw.$$

Note that the right-hand side is a constant as $n$ goes to infinity. Letting $c$ be the right-hand side, we have
$$\frac{x_{n+1}}{x_n} - 3^d= \frac{c}{x_n}.$$

Since $x_{n+1}$ is a bigger power of 2 than $x_n$, $\dfrac{x_{n+1}}{x_n}$ is always an integer. That means the right-hand side is always an integer as well. Since $\dfrac c{x_n}$ goes to $0$ as $n$ goes to infinity, it must become 0 eventually.

Well, when it does become 0, we have $\dfrac{x_{n+1}}{x_n}=3^d$, which cannot happen since the left-hand side, a power of 2 that is greater than 1, can never be a power of 3.

Here is an easy exercise.

Exercise. Check that the above proof works the same if you replace 3 by any positive integer that is not a power of 2.


How fast can we optimally cluster 1-D data?

Here's what my search has come up with:

There's a straightforward dynamic programming solution of the problem in this case, which requires $\mathop{\Omega}\left( k \cdot n^3 \right)$ time; and with some thought one can avoid redundant computation of sums-of-squares by this algorithm, reducing the complexity to $\mathop{\Omega}\left( k \cdot n^2 \right)$. This is described in:

  Wang, Haizhou, and Mingzhou Song. Ckmeans. 1d. dp: optimal k-means clustering in one dimension by dynamic programming. The R journal 3, no. 2 (2011): 29.

That being said - I'm thinking perhaps this can be improved to $\mathop{o} \left( k \cdot n \log{n} \right)$ somehow, or at least $\mathop{\omega} \left( k \cdot n^2 \right)$.


Finding Degree of match with Soundex or Metaphone

You can use K-nearest with the data points you have like % ,freq, or score of the edit and soundex algo.


I recommend looking into formal logic beyond vague, hand-wavy descriptions. It's interesting and highly relevant to computer science. Unfortunately, the terminology and narrow focus of even textbooks specifically about formal logic can present a warped picture of what logic is. The issue is that most of the time when mathematicians talk about "logic", they (often implicitly) mean classical propositional logic or classical first-order logic. While these are extremely important logical systems, they are nowhere near the breadth of logic. At any rate, what I'm going to say largely takes place in that narrow context, but I want to make it clear that it is happening in a particular context and need not be true outside of it.

First, if consistency is defined as not proving both $A$ and $\neg A$, what happens if our logic doesn't even have negation or if $\neg$ means something else? Clearly, this notion of consistency makes some assumptions about the logical context within which it operates. Typically, this is that we are working in classical propositional logic or some extension of it such as classical first-order logic. There are multiple presentations, i.e. lists of axioms and rules, that could be called classical propositional/first-order logic but, for our purposes, which doesn't really matter. They are equivalent in some suitable sense. Typically, when we are talking about a logical system we mean a (classical) first-order theory. This starts with the rules and (logical) axioms of classical first-order logic, to which you add given function symbols, predicate symbols, and axioms (called non-logical axioms). These first-order theories are usually what we're talking about as being consistent or inconsistent.

Next, soundness usually means soundness with respect to a semantics. Consistency is a syntactic property having to do with what formal proofs we can make. Soundness is a semantic property that has to do with how we interpret the formulas, function symbols, and predicate symbols into mathematical objects and statements. To even begin to talk about soundness, you need to give a semantics, i.e. an interpretation of the aforementioned things. Again, we have a separation between the logical connectives and logical axioms, and the function symbols, predicate symbols, and non-logical axioms. What makes connectives connectives and logical axioms logical axioms from the semantic point of view is that they get treated specially by semantics while function symbols, predicate symbols, and non-logical axioms do not. The typical semantics for classical first-order logic is to interpret formulas as set-theoretic relations on some (power of a) set called the "domain" given as part of a particular semantics, and the connectives as the more or less obvious set-theoretic analogues, e.g. $[\![\varphi\land\psi]\!]=[\![\varphi]\!]\cap[\![\psi]\!]$ where I use $[\![\varphi]\!]$ as the interpretation of the formula $\varphi$. In particular, $[\![\neg\varphi]\!]=D\setminus[\![\varphi]\!]$ where $D$ is the domain set. The idea is a formula is interpreted as the set of (tuples of) domain elements that satisfy the formula. A closed formula (i.e. one with no free variables) is interpreted as a nullary relation which is to say a subset of a singleton set which can only be that singleton or the empty set. A closed formula is "true" if it isn't interpreted as the empty set. Soundness is then the statement that every provable (closed) formula is "true" in the above sense.

It is easy from here, even from the sketch I've given, to prove that soundness implies consistency (in the context of classical first-order logics and the semantics I've sketched). $$[\![\varphi\land\neg\varphi]\!]=[\![\varphi]\!]\cap(D\setminus[\![\varphi]\!])=\varnothing$$ If your logic is sound, then every provable formula interprets as a non-empty set, but $[\![\varphi\land\neg\varphi]\!]$ is always interpreted as the empty set no matter what formula $\varphi$ is, and so it can't be provable, i.e. your logic is consistent.


What is wrong with the following $P$ problem?

Very simple: We can sort an array without checking every possible permutation. (Many times we don’t check any permutation of the array, we just re-arrange the order of items so we can guarantee the array is sorted, without ever checking it. )


Get specified bit in addition of two large binary numbers

Your method will indeed work, but for two $n$-bit numbers it will still take $O(n)$ time. There is a much faster way to solve your problem, with running time $\Theta(\log n)$, known as carry-lookahead addition. The downside is that in my experience teaching this technique, people have a hard time wrapping their heads around it. You can find online sources, here and here, and some algorithm or computer organization texts cover it. It's a really interesting algorithm, well worth taking the time to figure it out.


What is `wasted space` parameter and why is it O(n) for a linked list

Different people seem to define "wasted space" in different ways. Some authors define it as any space in a data structure that's not used to store actual data; others define it as space that could be used to store data but isn't being so used at the moment.

So, in the first definition, a linked list has $O(n)$ wasted space because every entry of the list contains some piece of data but also a pointer, so a constant fraction of the space taken up by the data structure is "wasted". (I think this is a silly definition of "waste": the space taken up by the pointers isn't wasted; it's an overhead.)  In the second definition, a half-full hash-table has 50% wasted space (again, $O(n)$).


In-place "clumping-by-color" algorithm faster than sorting by color?

If I understand correctly, you're asking if preserving the locations of grouped values will give a speedup over reordering them, so for instance {2,2,2,1,1,1} would be left in place instead of rewriting the array as {1,1,1,2,2,2}.  I would say no, because comparing-and-swapping is not slower than simply comparing in practice, and you probably need the same number of compares regardless.

I've done tests of different Dutch National Flag algorithms and found no variation in times between versions that do a lot of swaps vs. ones which do little (there was a period when that number was important, and a number of papers have been published on it).  They all do the same number of comparisons, but the mechanics of moving elements into cache, etc. seems to make swaps almost free.

As greybeard notes, you're probably using the wrong Quicksort.  Try the one described here:  https://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf .  2-way Quicksort is quadratic with duplicate values, for instance n duplicates will take o(n^2) since it will place all remaining values on one side of the pivot during each recursion.


How does one implement Dijkstra while skipping an edge

Check out Yen's Algorithm for finding the K-shortest paths using any shortest path algorithm. The link provided uses Dijkstra's algorithm as an example


Maximum Sum SubArray - Naive Implementation

An implementation that I wouldn't call naïve but criminally stupid would calculate the sum of elements in each subarray by adding up the elements. You are summing from 1 to n elements for each of n^2/2 subarrays, which makes it $O (n^3)$ (proving that this is a lower bound needs a bit more care).

Of course a naïve but not stupid implementation would calculate the sums for all subarrays starting with the first element using only one extra addition for each sum.


Allocating n processes to n servers, counting from the server perspective

The heuristic is: "try both ways, and see which works".  As you get more practice you might start to develop a sixth sense about which one to try first, but that's the most useful principle I can suggest.

The general mathematical principle is the bijection principle.  If you have two finite sets $S,T$ and you can find a bijection between $S$ and $T$, then they must have the same size.  So, if you can count the number of elements in either of them, you can infer the number of elements in the other one.


It looks like a Dijkstra algorithm to me.

I see the algorithm begins at the "do while" line and everything before are the input for the algorithm. With your clue that G is the goal node, and $t_{i,j}$ are lengths, it is easy to see $f_i$ is the distance from $i$ to G as we know so far within the loop.

So the algorithm means the following:

Every iteration, we find the node $j^*$ within T that has min distance to G
Then we scan each of its neighbor $i$, update their distance to G

update rule: they reach G with traversing $j^*$ or without (i.e., the old $f_i$), so min of these two will be the new known min distance to G

After this scan, all nodes that can possibly reach G via $j^*$ are updated. And we remove $j^*$ from T, meaning that in the future, any other node (not neighbor to $j^*$) to reach G via $j^*$ should only be via one of its neighbor $i$

Here the $t_{i,j}$ are positive, so that adding to $f_{j^*}$ can only increase the distance. And hence all $f_i$ will only be decreasing in each iteration. In this case, this algorithm is a dynamic programming by iteratively reducing the problem to a smaller set of nodes until a solution is found.


For any variable $X$, if there is a path from $X$ to $\neg X$ then you cannot set $X$ to $True$, since otherwise you would end up with a $True \Rightarrow False$ implication somewhere along the path. For the same reason, if there is a path from $\neg X$ to $X$ you cannot set $X$ to $False$.

Hence, in the first case you must set $X$ to $False$, in the second you must set it to $True$. If there are paths in both directions, as you already know, the formula is not satisfiable.

In your example, there are only paths from $X$ to $\neg X$ for all variables, hence the only assignment that satisfies the instance is the one where all variables are $False$.


Making feature vector from Gabor filters for classification

Well I figured it out myself that making a 1D vector of [1x80] by appending two [1x40] array worked and my classifier works very fine now


Why is the second operation of a Monad called bind?

In Haskell the syntactic sugar for bind e₁ (λ x . e₂) is

do x ← e₁
   e₂

That is, the result of the computation e₁ is bound to x, after which e₂ is computed.

In ML-like languages the same thing is written as

let x = e₁ in e₂

which again is a form of binding a variable to a value.

As for return being a control-flow mechanism – that's precisely what it is. You are probably thinking of control mechanisms for branching, looping, raising exceptions etc. Well, return is the one that ends a computation and yields a result.


lambda calculus reduction: (((lambda f (lambda x (f x))) (lambda y (* y y))) 12)

Lambda expressions are evaluated by reducing the leftmost redex first.  A redex is something of the form $(\lambda a.b)c$ .  Your expression is $(\lambda f.\lambda x.fx)(\lambda y . *yy)~12$.  So your first redex is

$$(\lambda f.\lambda x.fx)(\lambda y . *yy)$$

So you substitute $(\lambda y . *yy)$ for $y$ in $\lambda x.fx$ to get $$\lambda x.(\lambda y . *yy)x~ 12$$

Then your next redex is the entire expression, ($(\lambda y . *yy)x$ is also a redex but it isn't the leftmost one) substituting $12$ in for $x$.  So you get $$(\lambda y . *yy)~12$$

Then your last redex is the entire expression again so you get

$$*~12~12$$


Why can we not find the generally superior machine learning algorithm in practice?

There are many dimensions that "intelligence" could potentially be measured on.  We already know of some artificial intelligence schemes that do better than humans on some dimensions.

It's true that we don't have artificial intelligence schemes that do better than humans, on the sorts of problems that tend to arise in practice as part of everyday human life and experience.  On the other hand, humans have had hundreds of millions of years to evolve and adapt.  Artificial intelligence has only been around for maybe half a decade.  That might be one possible explanation.

Separately: The question seems to be based on several misconceptions.  Let me point out a few things you've written, and try to clarify the misconceptions:

  The point is that our mind is a superior algorithm, it can figure out tradeoffs in a much more general case than any machine learning algorithm we have.

Our mind is better for some tasks, but not all.  There are other tasks where machines are better.  For instance, machines are superior at chess, or at adding up small integers billions of times in a row without making a single error.  Humans are superior at making other people laugh, cry, or feel better about themselves, or at folding laundry.

For instance, machines can solve Connect Four perfectly, but most people can't.  Thus, if we allow "performance at Connect Four" as one of the dimensions that we're measuring Pareto-optimality at, machines are Pareto-optimal: they dominate humans in at least one dimension.

Now what you're probably really asking is, why do humans dominate machines in most dimensions?  But to make that question well-defined, we have to define what is the set of all dimensions.  What's probably implicit in that question is the assumption that you mean "the set of all dimensions we (humans) care about", or "the set of all dimensions that are meaningful to us (humans)".  Now consider that the human brain has had hundreds of millions of years to evolve and get better at the dimensions that humans care about or that matter to us, whereas artificial intelligence hasn't.

  Furthermore, its Kolmogorov complexity is 4MB or less, and thus should be fairly easy to discover.

Actually, no, that doesn't follow.  Let's suppose for the sake of argument that an entire human organism can be described in 4MB of data (after compression; let's not quibble about whether that's actually biologically correct; and let's not worry about the fact that Kolmogorov complexity is primarily meaningful in an asymptotic sense, and ignore those issues), or equivalently, 32 megabits of data.

That means that a program that behaves like a human would require 32,000,000 bits of data to describe.  So, you're asking: Why is it hard to find such a program?  Perhaps implicit in your question is: How many programs can there be?  How hard can it be to find the right one?

The answer is: it might be very very hard.  There are $2^{32,000,000}$ possible programs (of that length).  That's an enormously large space -- and it's a space where maybe all but one of them are useless, and only one is any good.  Trying all of the possibilities is way beyond feasible: like, you couldn't do it within the lifetime of the universe, even if you imagine a universe full of supercomputers, where each atom in the known universe has the computational power of one of today's supercomputers.  $2^{32,000,000}$ is an unimaginably large number.

So, it shouldn't be such a great surprise that it might be hard to find an example of such a program explicitly.  Just because we know that it exists doesn't make it easy to find such a thing.

For instance, even if space aliens had landed 150 years ago and told us that there exists a proof of Fermat's last theorem, it still would have taken close to 150 years to find the proof.  Just knowing that a proof exists doesn't really help you in finding it.  I bet that the Latex source file for the papers that prove Fermat's last theorem correct could be compressed to less than 4MB.  Even if I tell you that there exists a proof whose Kolmogorov complexity is at most 4MB, it's still not at all easy to find that proof.


Why do we need to run the bellman-ford algorithm for n-1 times?

Answering your first question is simple. Try out a few graphs and see for yourself why it doesn't work. As to your second question, $n-1$ is the maximal length of a shortest path in the graph. After $k$ iterations of the Bellman–Ford algorithm, you know the minimum distance between any two vertices, when restricted to paths of length at most $k$. This is why you need $n-1$ iterations. Negative weights have absolutely nothing to do with it.

For a more sophisticated answer, consult the recent paper of Jukna and Schnitger, On the optimality of Bellman–Ford shortest path algorithm. They show that among the class of Bellman–Ford-like algorithms, the Bellman–Ford algorithm is optimal.


Reduce the total internal border of a set of touching rectangles (using graphs)

Here's a naive attempt at a greedy solution.

I'm assuming the initial input is a polyomino (polygon made up of grid aligned squares) on a grid as in your "real world example".

Let $b = (i, j, w, h)$ be the rectangle with lower left corner containing grid location $(i, j)$ with width $w$ and height $h$. A rectangle is valid if and only if all of its internal grid cells are part of the polyomino.

For a valid rectangel $r$, the boundary edges of $r$ will either also be boundary edges of the polyomino itself, or internal edges. Denote by $B_r$ the number of boundary edges of the rectangle that are internal to the polyomino and $I_r$ the number of grid edges that are internal to both the boundary and the rectangle. In the teal rectangle in my example below, $I_r = 17$ and $B_r = 6$ (the red sketchy edges). Now define the quality of the rectangle $r$ to be $Q_r = I_r - B_r$.

The thought here is that the quality of a rectangle measures how good it is at eliminating internal edges.

Now, the greedy solution I have in mind is:

Generate all of the $O(n^4)$ possible rectangles $r$.
For each rectangle $r$, check if $r$ is valid.
* If $r$ is valid, compute its quality score and maintain the rectangle with the maximum quality.
End for loop.
Add the rectangle that maximized the quality to the output set, and color the squares it covers white. Repeat until all squares are white.

Unfortunately this is $O(n^5)$ where $n$ is the width and height of the grid. But if your problem size really is like the image, then that may not be an issue.

Also, I don't have a proof that it's optimal, but I'll think about it.

Ok, I wrote some code for this. It's quick and dirty, but it returns exactly your optimal result on your original small example. It is quick and dirty, so don't judge ;).

from functools import reduce

# Generates all valid rectangles that have a lower left hand corner in i and j
def validRectanglesFrom(grid, i, j):
    result = []
    w = 1
    while i + w <= len(grid) and grid[i + w - 1][j] == 1:
        h = 1
        row_is_valid = True
        while j + h <= len(grid[i + w - 1]) and row_is_valid:
            for k in range(i, i + w):
                if grid[k][j + h - 1] == 0:
                    row_is_valid = False
                    break
            if row_is_valid:
                result.append((i, j, w, h))
            h = h + 1
        w = w + 1
    return result

def left_edge_is_internal(grid, i, j):
    return i > 0 and grid[i - 1][j] == 1 and grid[i][j] == 1

def right_edge_is_internal(grid, i, j):
    return i < len(grid) - 1 and grid[i][j] == 1 and grid[i + 1][j] == 1

def bottom_edge_is_internal(grid, i, j):
    return j > 0 and grid[i][j - 1] == 1 and grid[i][j] == 1

def top_edge_is_internal(grid, i, j):
    return j < len(grid[i]) - 1 and grid[i][j] == 1 and grid[i][j + 1] == 1

def bottom_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda i: bottom_edge_is_internal(grid, i, rect[1]),
                    range(rect[0], rect[0] + rect[2])
                )
            )
        )
    )

def top_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda i: top_edge_is_internal(grid, i, rect[1] + rect[3] - 1),
                    range(rect[0], rect[0] + rect[2])
                )
            )
        )
    )

def left_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda j: left_edge_is_internal(grid, rect[0], j),
                    range(rect[1], rect[1] + rect[3])
                )
            )
        )
    )

def right_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda j: right_edge_is_internal(grid, rect[0] + rect[2] - 1, j),
                    range(rect[1], rect[1] + rect[3])
                )
            )
        )
    )

def boundary_penalty(grid, rect):
    return (
        bottom_boundary_penalty(grid, rect) +
        top_boundary_penalty(grid, rect) +
        left_boundary_penalty(grid, rect) +
        right_boundary_penalty(grid, rect)
    )

def internal_grid_edges(rect):
    return ((rect[2] - 1) * rect[3]) + (rect[2] * (rect[3] - 1))

def quality(grid, rect):
    return internal_grid_edges(rect) - boundary_penalty(grid, rect)

def get_rectangles(grid):
    result = []
    grid_locations = [(i, j) for i in range(0, len(grid)) for j in range(0, len(grid[i]))]
    unfilled = {cell for cell in grid_locations if grid[cell[0]][cell[1]] == 1}
    while len(unfilled) > 0:
        rects = [rect for cell in unfilled for rect in validRectanglesFrom(grid, cell[0], cell[1])]
        qualityScores = list(map(lambda rect: quality(grid, rect), rects))
        bestRectIdx = reduce(lambda i, j: i if qualityScores[i] > qualityScores[j] else j, range(len(qualityScores)))
        bestRect = rects[bestRectIdx]
        result.append(bestRect)
        for i in range(bestRect[0], bestRect[0] + bestRect[2]):
            for j in range(bestRect[1], bestRect[1] + bestRect[3]):
                unfilled.remove((i,j))
                grid[i][j] = 0
    return result

# Your initial example
grid = [[1, 1, 1], [0, 1, 0], [0, 1, 1], [0, 1, 0]]
get_rectangles(grid)

# Your "real world" example
grid2 = [[0,0,0,0,0,0,0,0,1,1,1,0,0,0,0],
        [0,0,0,0,0,0,0,0,0,0,1,1,1,0,0],
        [0,0,0,0,0,0,0,0,0,1,1,1,0,0,0],
        [0,1,0,0,0,0,0,0,0,1,0,1,1,0,0],
        [1,1,0,0,0,0,0,0,0,0,0,1,1,1,0],
        [1,1,1,1,0,0,0,0,1,0,0,1,0,1,0],
        [0,0,0,1,1,0,0,1,1,1,1,1,0,1,0],
        [1,1,1,1,1,0,1,1,1,1,1,1,0,0,0],
        [1,1,1,0,1,0,1,1,1,1,1,0,0,0,0],
        [0,0,1,1,1,1,1,0,0,1,1,1,0,0,0],
        [0,0,0,1,0,0,0,0,0,0,1,0,0,0,0],
        [0,0,0,1,1,1,0,0,0,0,0,0,0,0,0],
        [0,1,1,1,0,1,1,0,0,0,0,0,0,0,0],
        [0,1,1,1,0,1,0,0,0,0,0,0,0,0,0],
        [0,1,0,1,1,1,1,1,0,0,0,0,0,0,0]]
get_rectangles(grid2)

Here's the result my code returns for your "real world" example.


In a flow network, is it possible to restrict the flow going into a node?

I believe you can represent node N as two nodes, A and B. Node A has all of the inbound flow edges of N, and Node B has all of the outbound flow edges of N. Nodes A and B are connected by a single edge which you can use to throttle the flow. The edge from A to B is the only edge out of A and the only edge into B.


It is possible to build a Turing machine with "Lego" elements without any electric components, only with pneumatic transmission of energy. The guys who did this used some logic gates with pneumatic but this was the very easy part. The underlying automaton was way harder to build. (webpage in French. The other Turing machines in Legos use electronic devices which is very much like cheating)

Moreover I know you can build logic gates using only Lego elements and that may be more relevant.

So mechanics as well as pneumatics are enough to build logic gates.


Finding the number of squares by connected coordinates

Let $b(p, \ell)$ be a boolean value denoting whether the horizontal segment whose left endpoint is $p$ and whose length is $\ell$ exists. Then the values of $b(p,\ell)$ for all possible $p$ and $\ell$ can be computed in $O(n^3)$ recursively using the fact that

  $b(p,\ell)$ is true iff $b(p,\ell-1)$ is true and $b(p+\ell-1,1)$ is true where $p+\ell-1$ denotes the point on the right side of $p$ and the distance between them is $\ell-1$.

Here $n$ is the length of the grid.

Similarly, you can do the same thing for vertical segments.

Now you can check each possible square by checking its four edge segments. The whole running time is $O(n^3)$.

As j_random_hacker said in the comment,

  You can drop the space usage to $O(n^2)$ by instead calculating the length $w(p)$ of the longest horizontal segment having left endpoint $p$ for all $p$. Then $b(p,\ell)=(w(p)\ge\ell)$.


Minimal shift operations to sort an array

The problem is actually quite simple. When shifting the element at the front, find the last element that is greater than it, and put it after that element.

The number of shifts this takes is $n -k$ where $k$ is the length of the longest increasing suffix of the input.


Handling dead state in NFA to DFA conversion

Your DFA actually looks correct. Why do you need a dead state?

A dead state means the automaton was given a prefix of an input that will never lead to an accepting state. But the language of the NFA has no such prefixes - whatever the prefix is, if you add "10" or "11" you will get  to an accepting state.

Anyways, the right thing to do now is to verify that the DFA works fine for several sample inputs. More generally, to prove it actually does decide the language generated by $(0+1)^*1(0+1)$.


Why are binary numbers sometimes written with one or more leading zeros that don't change the number (quantity) represented?

Leading zeroes in binary usually indicate the bit length of the data type.
For example, the number 110 represented in a 4 bit data type would be 0110.
Even if there is no data type specified, it's sometimes common to pad your binary numbers to the next power of 2. For example, 10111 of size 5 should be padded to 8 $(2^3)$ as 00010111


What exactly representational bottleneck in InceptionV3 means?

Cool question! I managed to start thinking about its meaning thanks to your asking.

I believe you would like to consider it in the sense of information flow. As the information is compressed to a same size in both cases, the question is which one is more effective. Information with amount of 35*35*640 can flow through a wider pipe more freely. A pooling layer just prunes information directly in the left solution, while doing Inception in the right case expands the representation to a more sparse space and makes meaningful inferences before get pruned. Think of the pooling operation in left as a neck or a narrow path, and the middle representation in right as a broad lake. The pooling layer in right can also select better output since the source has more abstract (semantics) information.

As to figure 10, I consider it as a balance between the representation size and the computation burden.


Your problem is NP-hard. To see this, you can reduce it from the minimum test cover (or test collection) problem: given a set $X$ of $\ell$ elements and a collection $C = \{C_1, \dots, C_k \}$ of $k$ subsets of $X$, find a minimum test cover for $X$ and $C$, i.e., a subset $C'$ of $C$ that has minimum size and satisfies the following property: for every pair of distinct elements $i,j \in X$ there is a set in $C'$ that contains exactly one of $i$ and $j$.

The reduction is as follows: for each element $x \in X$ create a number of $k$ bits $b_1,\dots,b_k$ where $b_i = 1$ if and only if $x \in C_i$.
There is a test-cover $C' = \{ C_{i_1}, C_{i_2}, \dots \}$ if and only if the $|C'|$ bits in positions $i_1, i_2, \dots$ suffice to distinguish all input numbers.

Since the above reduction sets $m=\ell$, the measures for two corresponding solutions of test-cover and your problem coincide, and test cover is not approximable within a factor of $o(\log \ell)$, this also shows that your problem is $o(\log m)$-inapproximable.

On the bright side, the converse reduction works too: given an instance of your problem you can create an instance of minimum test cover by considering the set $X$ containing your $\ell = m$ input numbers $x_1, \dots, x_m$ and $C = \{C_1, \dots, C_k \}$ as a collection of $k = n$ sets where $C_i = \{ x \in X \mid \text{the $i$-th bit of $x$ is } 1 \}$. This means that the $O(\log \ell)$-approximation algorithm for minimum test-cover immediately translates to a $O(\log m)$-approximation algorithm for your problem.

See this paper and this paper.


Set of steps that cannot be implemented on a Turing machine

The Church–Turing thesis states that every algorithm can be implemented on a Turing machine. It has stood the test of time. In particular, I believe that the answer to your question is negative.

The appearance of quantum algorithms, in particular Shor's factorization algorithm, has called into question the efficient Church–Turing thesis (sometimes known as the Cook–Karp thesis), which states that $\mathsf{P}$ captures the class of efficiently solvable problems; but quantum computers are known to compute the same class of languages as classical computers.


Sources on dictionary learning and related algorithms

The best resource, in my opinion, is eDx - Sparse Representations in Signal and Image Processing: Fundamentals by Michael Elad.


How to prove that there is no better algorithm

I presume that $L$ is the length of $D_m$ for all machines.
Hence your input is of size $O(|M|\cdot (L+|A|))$ because it contains $|A|$ activities for all machines and the $D_m$ array of length $L$ for all machines. Your runtime is $O(|M|\cdot (L+|A|))$. Thus your algorithm runs in linear time with respect to your input
(meaning your algo is not pseudo-polynomial it is in fact polynonmial and even linear).
If a value in $D_m$ could be below $0$ we would have to check every value in $D_m$ for every machine at least once and for every activity that $D_m$ is large enough making the minimum runtime $\Omega (|M|L + |M||A|) = \Omega (|M|(L+|A|))$ and thus your algo optimal.


Algorithm for animating/morphing convex polygon diagrams

If your initial set of polygons is a power-diagram, you can insert a new polygon by inserting a new center and growing its power circle smoothly. You don't have direct control of the polygons but rather of the underlying power circles. Power diagrams as Voronoi diagrams are always made of convex polygons.
https://diglib.eg.org/bitstream/handle/10.2312/evs20201057/109-113.pdf
Another way is to subdivide one of the polygons slicing it with a straight line, similar to a spatial partition tree, to ensure the resulting polygon is still convex. http://proceedings.mlr.press/v84/fan18b/fan18b.pdf


Formal Description Of Data Structure For Infinite Sets Of Reals

I'm not sure you need to reference any prior work; it's a basic enough approach.  You can just say that you represent a set as a union of intervals.  If you were inspired by Sympy, you could cite Sympy and that page.


For a netmasked IP address xxx.xxx.xxx.xxx/N, convert each xxx octet in the address to binary.  The masked address is the leftmost N bits with all other bits replaced with zeroes.

So 10.0.0.2/2 becomes 00001010 00000000 00000000 00000010 which is then masked to 00000000 00000000 00000000 00000000, because 00 are the leftmost 2 bits.

90.0.0.0/4 becomes 01011010 00000000 00000000 00000000 which is then masked to 01010000 00000000 00000000 00000000, because 0101 are the leftmost 4 bits.


Arithmetic Encoding vs Adaptive Arithmetic Encoding

The pseudocode looks good to me, except of course that in static arithmetic coding, you need to transmit the model before the decoder can use it.
Exactly how to do that in a space-efficient way is not obvious. One of the advantages of adaptive coding is that it gives you that for free: the loss of compression while the model is "learning" should be (if you did it correctly) exactly the minimal cost of transmitting the model.
But, of course, it's not free because updating an adaptive model isn't free. You pay for it in the CPU and memory efficiency of the encoder and decoder.


Hardness of a problem related to set cover

Hine: Given an instance of set cover, add $k-1$ copies of the set $\{1,\ldots,n\}$.


I think you can solve this using this construct:

$$S \rightarrow ASA|BSB|ATA|BTB $$
$$T \rightarrow CAZC|CBZC$$
$$Z \rightarrow AZ|BZ|\epsilon$$
$$A \rightarrow a , B \rightarrow b, C \rightarrow c$$

First rule provides the $w$ and $w^R$ in the language, second rule makes sure $v \ge 1$ and has 1 c in both sides and third is just constructing the $v$ further. My assumption was your arrow on top of last $w$ was just meant it is reversed.


I would suggest you to use a hierarchical K-means, or a hierarchical vocabulary tree approach. For example:

http://gecco.org.chemie.uni-frankfurt.de/hkmeans/H-k-means.pdf
http://www.vlfeat.org/overview/hikm.html

CVPR Paper with application:
http://www.vis.uky.edu/~stewe/publications/nister_stewenius_cvpr2006.pdf

FLANN also has some kind of hierarchical capabilities.


Clustering of Songs (The Joe Walsh Problem)

What you want to do seems to be known as Audio Feature Extraction or, more specifically, Music Information Retrieval, that is automated methods that distill characteristics out of (sets of) music files. You would have to extract features of samples of both equivalence classes and look at differences that can inform song choice.

Researchy tools are available for instance here and here. A finalist of Google Science Fair 2011 presented interesting stuff but I can not find his tools anywhere.


What is the correct definition of coNP/poly?

Recall that a decision problem is a language $L \subseteq \{0,1\}^*$.  (This is the language of all words $w$ such that the answer to the yes/no question is "yes".)
In this context, a Turing machine solves a decision problem $L$ if $L$ is the language accepted by that Turing machine.  In other words, when run on input $w$, the Turing machine halts and accepts if $w \in L$, and halts and rejects if $w \notin L$.


How to divide an unsorted list in linear time where every element in the first part is smaller than every element in the second list

Use the median of medians with quickselect allows you to find the $k$th element in linear time. Set $k = n/2$ to find the exact median and use it to partition your array in one more linear time step.


So the difficulty is to determine $dp[u]$, depth of $u$, starting from the list of its sons depths $L[dp[v]]$.

Once $L[dp[v]]$ is sorted in a heap, you can recursively and greedily pop the 2 minimum values $i$, $j$ and push $1+max(i, j)$.

For instance, $L[dp[v]] = [7,5,5,4,3,2,2]$:

=> [7,5,5,4,3,3]
=> [7,5,5,4,4]
=> [7,5,5,5]
=> [7,6,5]
=> [7,7]

$dp[u] = 8$

This is actually $O(nlog(n))$ due to the heap sort.


Are all Recursively Enumerable languages which are not Recursive also Undecidable?

A language is recursive (newer terminology: computable, also decidable) is there is a Turing machine that always halts that recognizes the language. It is recursively enumerable (new: computably enumerable) if there is a Turing machine that accepts it (it halts and accepts for strings in the language, it might never halt for strings not in the language). If the language is not recursive, it isn't decidable ("recursive" and "decidable" are alternative terms for the same class of languages).


A little confusion with the Knapsack problem (a worked example)

The (non-negative) variables $x_1,x_2,x_3,x_4$ must satisfy the constraint
$$ 2x_1+2x_2+4x_3+5x_4 \leq 8. $$
If $x_1=x_2=1$ then this simplifies to
$$ 4x_3+5x_4 \leq 4, $$
which implies in particular that $x_3 \leq 1$ and $x_4 \leq 4/5$ (since $x_3,x_4 \geq 0$).


Priority data structure supporting operations Insert, Delete, Get in O(log n)

Store the items in a balanced binary tree, sorted by key.  Augment each node of the binary tree to have a pointer to the lowest-priority element within the subtree rooted at that node.  This allows you to implement all three operations in $O(\log n)$ time.

Details: Whenever you insert or delete an element, you can follow the path from that element to the root, updating the augmented data inside each node you visit as you go.  This enables you to implement Insert and Delete in $O(\log n)$ time.  Any interval of keys can be expressed as the union of $O(\log n)$ subtrees, so the Get operation only needs to examine the augmented data inside $O(\log n)$ nodes and thus can be implemented in $O(\log n)$ time.


Showing a problem is NP complete? Reducing CLIQUE to KITE.

With regards to the reduction, you need to show that given an oracle for Kite, you can solve Clique in polynomial time. It doesn't really help that every Kite has a Clique in it: we're interested in solving Clique, but a graph that has a Clique doesn't necessarily have a Kite (if it has a Kite, then it certainly has a Clique - but that's not enough). You need to modify the graph so that if(f) it has a Clique, then it also has a Kite and pass that modified graph as an input to the oracle.

We don't ordinarily believe that an NP-complete problem can be solved in polynomial time. The point of a verifier/certifiate is that with help, we can solve it in polynomial time. The certificate is the "help", and you can define the certificate to be almost anything you like. For instance, for Clique, we can ask that the certificate be a list of the vertices that make up the Clique. Verifying then becomes easy: we can check we've indeed been given $k$ vertices, and that there are edges between all of these vertices. If you like, you can think of the certificate as a solution to the problem, and the verifier's job is to check that the solution is correct.


How does Command Z work through computer commands?

You should really try to implement this yourself, and then it will become quite obvious.
You define a stack where you put all the operations that the user performs.  Here are some examples:

Close window
Move file from one directory to another
Create file
Move icon on Desktop from $(x_1,y_1)$ to $(x_2, y_2)$
Type a character
Delete a character
Copy to clipboard

All of these operations have reasonable "inverse" operations.:

Close window → Reopen window
Move file from A to B → Move it back to A
Create file X → Delete file X
Move icon from pos1 to pos2 → Move it back to pos1
Type a character → Delete the previous typed character, etc.

When the stack contains "reversable" operations, the undo command simply pops the last operation off the stack and performs its inverse operation.
Some operations are not reversable, though, such as posting on the Internet, and permanently deleting a file.


Finding issues in concurrent implementation of carpark overflow control

For the first task think about what might happen, if the loop in Overflow is not run for each car.

For the second task, look at the following things:

How is the opening and closing of bars linked to arriving cars?
Does the overflow bar really open at the $100-\max$-th car?
The specification requests a specific order of opening and closing the bars. Is this enforced?

In the third task you should address the problems identified in the first two tasks by adding semaphores and possibly additional variables and atomic operations to the code.

Concerning your attempt and the questions therein:

The setting as described assumes that no car leaves the car park.
You may assume that eventually 100 cars will have arrived. (Otherwise you could not ensure termination.)
You should mostly keep the operations m1-m4 and o1-o3 (depending on your approach you might change one or two of them). Just add additional code around and inbetween them, in order to address the problems.
You use $100+\max$ twice, where you probably intended to use $100-\max$.
Using max in Process Main is changing its scope, since in the original code it is a variable local to Process Overflow.
Also your code does not solve most of the problems I hinted at for task 2. (This is no surprise, given that you had not identified them, when writing the code.)


NP-complete problem of partitioning into several sets with a Hamiltonian cycle

You can map any $\text{HamiltonianCycle}$ instance $G$ to an $L$-instance $(G, 1)$, yielding a polynomial time reduction from an $\mathsf{NP}$-complete problem to $L$ which implies the $\mathsf{NP}$-hardness of $L$.


How to classify a 3D "Knapsack" problem where the only limitation is space, i.e. there is no weight constraint?

In the standard Knapsack problem (solvable by DP) when we are packing objects we do not care about how we put objects in the knapsack, i.e., what only matters is a subset of objects and the sum of weights of these objects. But, in cuboid/rectangle packing problem the configuration of the cubes/rectangle is important to achieve the optimal packing. So, from this point of view these problems are different. I googled and found this heuristic approach and this article.


Minimizing sum of recursive pairwise sums

This problem can be solved using a min heap. You have to construct a min heap initially with all the elements of array. Now you simply take the top element of this heap and add it to the next top element of heap. Then reinsert the sum obtained in the heap. Keep a variable to track the total cost. This will ensure that you are adding the minimum elements and the final cost is minimum. This is analogous to the problem of connecting n ropes with minimum cost.


why does ${a^nb^n}$ fit the pumping lemma for context-free languages?

This language satisfies the conditions of the Pumping lemma. (By the way, your question title is wrong: you are not asking why it is context-free; you are asking why it satisfies the conditions of the lemma, which it does.)

Take the string s=a^mb^m and assume m>0. Don't use p or n, otherwise it is confusing, because those letters are used in the lemma. Now let v="a", y="b", x="", u=a^(m-1), z=b^(m-1).

You can definitely pump it as much as you want. In other words, you take a string such as aaaaaabbbbb, then you pick the two middle letters: aaaa ab bbbb. Then you pump them: aaaa aaabbb bbbb. Still in the language.


How does size of a number in an array affect time complexity algorithm analysis?

Actually, you can avoid any higher precision calculations.

Assume you are adding n k-bit numbers in one array, and adding n+1 k-bit numbers in the other array. The difference is a k-bit number (the one extra number that was added to the other array).

So you can perform the addition, and just ignore anything beyond k bits. Instead of getting the sum, you get the sum modulo $2^k$, but that is enough to get the correct result.


Textbook on formal syntax (and semantics) of programming languages

Maybe you will like to book Concrete Semantics (which is freely available as a PDF). It defines the syntax and semantics of an imperative programming language using the proof assistant Isabelle/HOL. In later chapters also types are added to the language and several examples of program analysis are shown.


What is the big O for $n^{\log n} + n!$?

Look at this
$$(\frac{n}{e})^{\log{n}} = \frac{n^{\log{n}}}{n} = n^{{\log{n}}-1}$$
And compare it with $(\frac{n}{e})^n$ (as $e^{\log{n}} = n$, because of $\log$ function property). By multiplying $n$ to the above eqautation you will get $n^{\log{n}}$. Hence, just we need to compare $n$ and $(\frac{n}{e})^{n-\log{n}}$. So, definitely, we will find that the growth of $n!$ is much higher than $n^{\log{n}}$.


Does a Universal Turing Machine have more computational power than a non-universal one?

In short yes, a non-universal Turing Machine is not Turing-complete.

The key part is that a computational model is Turing-complete if it can simulate any Turing Machine (or using the transitivity of the simulations, if it can simulate a Universal Turing Machine).

As you note, many Turing Machines are not Universal, they compute something, but they can't simulate any computation that any Turing Machine could do.

A possibly intuitive practical way of thinking about this is that Turing Machines are normally equivalent to programs - they take a particular type of input and compute some output. Universal Turing Machines are equivalent to programming languages or computers - you can build/run any program/Turing Machine on them. Of course I'm using "equivalent" very loosely here.


Optimal Page Replacement Algorithm - If more than one frame will not be used again, which one gets replaced?

The optimal algorithm uses whatever is optimal (or one of the optimal possibilities, in case there are several), i.e. whatever produces the least page faults. There isn't necessarily any simpler description of its behavior, though there might be. In general, it depends on the problem; for this specific problem, I don't know whether a simple description exists, though there is probably a simple algorithm that finds an optimal sequence.

FIFO, most used and LRU are heuristics that are useful for the online version; it's not necessarily true that they can be used in any shape or form to obtain optimal page replacement sequences (but you might be able to describe rules for obtaining an optimal sequence using them; I just don't know).


Return the subset with smallest cardinality of an array whose elements sum to at least a given value

First, we randomly select an element that is not the smallest one as a pivot, and partition the elements into two subsets: the ones less than the pivot ($P$) and the ones no less than the pivot ($Q$). Let $S$ be the sum of elements in $Q$.

If $S=C$, then $Q$ is exactly the optimal subset we want.
If $S<C$, then the optimal subset is the union of $Q$ and the subset with smallest cardinality of $P$ whose elements sum to at least $C-S$, which can be found by recursively applying this algorithm on $P$.
If $S>C$, then the optimal subset is the subset with smallest cardinality of $Q$ whose elements sum to at least $C$, which can be found by recursively applying this algorithm on $Q$.

Let $T(n)$ denote the expected running time of this algorithm on an input of $n$ elements, we have
$$T(n)\le \frac{1}{n-1}\sum_{i=1}^{n-1} T(\max\{i,n-i\})+cn,$$
where $c$ is a constant. By mathematical induction we can conclude that $T(n)\le 4cn$, thus the algorithm runs in expected linear time.

You can also use the idea of median-of-medians to get a worst-case linear time algorithm by selecting the pivot as the apporximate median produced by the median-of-medians algorithm.


Trying to understand interpretation and denotation in FOL

Consider the expression $+(x,\times(y,y))$, which is the FOL way to write $x+(y\cdot y)$. If I substitute $x=3$ and $y=5$ and do the arithmetic over the integers, what do I get? I need to evaluate the expression recursively.

In order to evaluate $+(x,\times(y,y))$, I need to evaluate $x$, to evaluate $\times(y,y)$, and then to combine them using the function $+$.

Evaluating $x$ is easy, since $x$ is just a variable. My assignment says that $x=3$, so the value of the expression $x$ is $3$.

Evaluating $\times(y,y)$ is more difficult. First I need to evaluate $y$ (twice) - as before, this is easy, and gives the result $5$. Now I need to combine the two values $5,5$ using the function $\times$. I have a large table which, for every pair of integers $a,b$, tells me what $\times(a,b)$ is. Looking at the table, I find out that $\times(5,5) = 25$.

Now that I have evaluated $x$ To $3$ and $\times(y,y)$ to $25$, I can finally look at the table for $+$ and deduce that $+(3,25) = 28$. So $28$ is the value of the entire expression.

The formal definitions you quote in your question attempt to capture the preceeding process in an abstract form. It's best if you work out the correspondence on your own.


How does one efficiently produce all binary sequences with an equal number of 0's and 1's?

Obviously there are $4^{n}$ binary strings of length $2n$. To traverse the binary an algorithm has to visit each node once, i. e. it has to do
$$ \sum_{i=0}^{2n} 2^i = 2^{2n+1} - 1 = \mathcal{O}(4^n)$$
steps.

Let's consider a recursive algorithm which traverses the tree you described, but counts the number of ones and zeros on its way, i. e. it will only traverse the good part of the tree.
But how many such binary strings with $n$ 0's and $n$ 1's are there? We choose $n$ 1's for our strings of length $2n$ and use Stirling's formula in step 2:
$$ {2n \choose n} = \frac{(2n)!}{(n!)^2} = \frac{4^n}{\sqrt{\pi n}} (1 + \mathcal{O}(1/n))$$

EDIT
Thanks to Peter Shor's comments we can also analyse the number of steps needed by the second algorithm, which counts the 1's and 0's. I'm citing his comment from below:

  We want to find all binary sequences with exactly $n$ 0's and $n$ 1's. We traverse the binary tree where each node is a sequence of at most $2n$ 0's and 1's. We don't need to visit any node with more than $n$ 0's or more than $n$ 1's. how many nodes do we need to visit? There are ${i+j \choose i}$ strings with $i$ 0's and $j$ 1's. Summing this over all $i,j \leq n$ gives $\sum_{i=0}^n \sum_{j=0}^n {i+j \choose i} = {2n+2 \choose n+1} − 1$. Now, we need to visit each of these nodes at a constant average cost per node. We can do this by visiting each left child first, and each right child second.

Using Stirling's formula again we obtain
$$ {2n + 2 \choose n + 1} - 1 = 4^{n+1} \frac{1}{\sqrt{n+1}} (1 + \mathcal{O}(1/n)) - 1 = \mathcal{O}(\frac{4^n}{\sqrt{n}}) $$
as the running time of the new algorithm.


Logarithmic reduction to another LOGSPACE problem

You are asking two questions. I will only answer the one about division. Division can be done in logspace, as shown in this answer, which cites the relevant literature.

However, in your case you are interested in division by 2, which is easier than general division. I bet you can show yourself that numbers can be divided by 2 in logspace (assuming that they're represented in binary). This operation is known as right shift.


Why can't we solve the dinner party problem by finding a maximum matching?

The problem is that you can not model all instances of the problem in the way you suggest: A person can be 'not on speaking terms' with arbitrarily many other persons, but an edge in a graph can only be connected to two vertices. So instances where someone doesn't want to speak to 3 or more other people cannot be modeled.


What is a the fastest sorting algorithm for an array of integers?

In general terms, there are the $O(n^2)$ sorting algorithms, such as insertion sort, bubble sort, and selection sort, which you should typically use only in special circumstances; Quicksort, which is worst-case $O(n^2)$ but quite often $O(n\log n)$ with good constants and properties and which can be used as a general-purpose sorting procedure; the $O(n\log n)$ algorithms, like merge-sort and heap-sort, which are also good general-purpose sorting algorithms; and the $O(n)$, or linear, sorting algorithms for lists of integers, such as radix, bucket and counting sorts, which may be suitable depending on the nature of the integers in your lists.

If the elements in your list are such that all you know about them is the total order relationship between them, then optimal sorting algorithms will have complexity $\Omega(n\log n)$. This is a fairly cool result and one for which you should be able to easily find details online. The linear sorting algorithms exploit further information about the structure of elements to be sorted, rather than just the total order relationship among elements.

Even more generally, optimality of a sorting algorithm depends intimately upon the assumptions you can make about the kind of lists you're going to be sorting (as well as the machine model on which the algorithm will run, which can make even otherwise poor sorting algorithms the best choice; consider bubble sort on machines with a tape for storage). The stronger your assumptions, the more corners your algorithm can cut. Under very weak assumptions about how efficiently you can determine "sortedness" of a list, the optimal worst-case complexity can even be $\Omega(n!)$.

This answer deals only with complexities. Actual running times of implementations of algorithms will depend on a large number of factors which are hard to account for in a single answer.


Is the language { | p and n are natural numbers and there's no prime number in [p,p+n]} belongs to NP class?

Note that there's always a prime between $p$ and $2p$ for any $p$ thus we can eliminate $n$ as a complexity parameter, as for any non-trivial  instance we have $n < p$.

The complement (there exists a prime in range $[p, p+n]$) is quite easy  (due to the shoulders of giants). There are various well-known polynomial size certificates of primality of $q$ you could return along with some $q \in [p, p+n]$ if that prime $q$ exists. Thus your language is in co-NP.

However the question of whether it is in NP or not seems very hard to me. Our input size is $b$ such that $2^b \approx p$. You need the existence of a $O(b^c)$ sized certificate that in the worst case asserts the compositeness of an exponentially large ($|[p, p+n]| \approx |[p, 2p]| \approx p \approx 2^b$) series of consecutive integers. From my intuition about number theory, finding such a certificate would be a major result, but disproving its existence would be as well. But perhaps someone with more number theoretic knowledge than me can pitch in if either of those turn out to be easy.


Your attempt does not work. Note that $s_1$ is never executed. (And if you prepend the right-hand side with "$s_1;$", it will be executed multiple times.)

What you can do is to translate the for loop into an equivalent while loop:

$$\sigma,\text{for } s_1, e_1, e_2, s_2 \text{ endfor} \to \sigma, s_1; \text{while } e_1 \text{ do } s_2; e_2 \text{ endwhile}.$$


Given matrix $A$, find vector $x$ such that every entry of $Ax$ is nonzero

Define
$$
M = 1 + \frac{\max_{ij} |A_{ij}|}{\min'_{ij} |A_{ij}|},
$$
where the minimum is taken over all non-zero entries. Then the vector $x$ given by $x_j = M^{j-1}$ satisfies your condition.

Indeed, consider some row $A_{i\cdot}$, and suppose that $A_{ik} \neq 0$ but $A_{i\ell} = 0$ for all $\ell > k$. Suppose, without loss of generality, that $A_{ik} > 0$ and that $\min'_{ij} |A_{ij}| = 1$. Then
$$
(Ax)_i = \sum_{j=1}^k A_{ij} M^{j-1} \geq M^{k-1} - (M-1) \sum_{j=1}^{k-1} M^{j-1} = 1.
$$

Whether the encoding of $x$ is small enough depends on your exact computation model.


There are various notions of optimality one can think of. One popular notion of optimality is worst-case running time, which is what you describe:

  An algorithm for solving a problem $P$ is asymptotically optimal with respect to worst-case running time if it runs in time $T(n)$, and any algorithm for $P$ runs in time $\Omega(T(n))$.

In fact, this notion is ambiguous, since it's not clear what the parameter $n$ is. Indeed, in some cases there are several relevant parameters, which we sometimes want to consider at the same time. This is the case with graph algorithms, in which there are two natural parameters: the number of vertices and the number of edges.

An additional point of ambiguity is the computation model against which everything is measured. In theoretical work, we usually consider the word RAM as our computation model, but other models are possible.

The definition above is about the asymptotic running time. This manifests itself in two ways. First, we only care about the time complexity of the algorithm up to constant factors. Second, we only care about the behavior for large $n$. In practice, sometimes $n$ is fixed, and then the definition above doesn't make any sense.

Whereas worst-case running time is a popular parameter, other parameters are also relevant. Some examples include average-case running time (whenever there is a natural input distribution) and memory consumption. Only you can say which notion of optimality is most relevant for you.


Finding big O notation of function with two parameters

Some of modifications of O described in Concrete Mathematics: Foundation for Computer Science says:

$ \qquad O(f(n)) + O(g(n)) = O(\mid f(n)\mid + \mid g(n) \mid) \qquad (9.22)\\
  \qquad O(f(n))O(g(n)) = O(f(n)g(n)) \qquad \qquad \qquad (9.26)
$

And using some basic knowledge of O notation and functions:

$
\qquad O(f(n) +c) = O(f(n)) \\
\qquad \forall_{n\in \mathbf N} \forall_{k>0} n^k > 0
$

Use those transformation you can came up with something like this:

$$\frac{n^{s+1}-1}{n-1}-1 = O\left(\frac{n^{s+1}-1}{n-1}-1\right) =
O\left(\frac{n^{s+1}-1}{n-1}\right) =
O\left(\frac{1}{n-1}\right)O\left(n^{s+1}-1\right) =
$$
$$
O\left(\frac{1}{n}\right)O\left(n^{s+1}\right) = O\left(\frac{n^{s+1}}{n}\right) = O(n^s)
$$

So your intuition was right.


Finding the length of the longest increasing path in a matrix

Here is an $O(nm \log nm)$ solution, where $n,m$ are the dimensions of the matrix. Later we improve it to an optimal $O(nm)$ solution.

Let $A[i_1j_1],\ldots,A[i_{nm}j_{nm}]$ be the entries of $A$ in non-decreasing order; the indices $i_tj_t$ can be computed in time $O(nm\log nm)$. We will compute a new matrix $B$ with the same dimensions such that $B[ij]$ is the length of the longest increasing part ending at $A[ij]$. We compute the entries of $B$ in the order $B[i_1j_1],\ldots,B[i_{nm}j_{nm}]$, using the formula
$$
B[ij] =
1 + \max_{\substack{i'j' \sim ij \\ A[i'j'] < A[ij]}} B[i'j'],
$$
where $i'j' \sim ij$ means that $A[i'j']$ is a neighbor of $A[ij]$, and we set $B[ij] = 1$ if the maximum is over the empty set.

The answer is simply the maximum entry of $B$. You can find an actual longest increasing sequence by starting with a maximum entry of $B$, say equal to $\ell$, finding a neighbor equal to $\ell-1$, then a neighbor equal to $\ell-2$, and so on until hitting a neighbor equal to $1$. This gives you a longest increasing sequence in reverse order.

As an example, consider your matrix
$$
A = \begin{pmatrix}
1&2&3&4\\2&2&3&4\\3&2&3&4\\4&5&6&7
\end{pmatrix}.
$$
We can order the entries as follows (there are many possible orders, since the entries are not distinct):
$$
A[1,1],A[1,2],A[2,1],A[2,2],A[3,2],A[1,3],A[2,3],A[3,1],\\A[3,3],A[1,4],A[2,4],A[3,4],A[4,1],A[4,2],A[4,3],A[4,4].
$$
We now compute $B$ in the same order:
$$
\begin{pmatrix}
1& & & \\
 & & & \\
 & & & \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2& & \\
 & & & \\
 & & & \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2& & \\
2& & & \\
 & & & \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2& & \\
2&1& & \\
 & & & \\
 & & &
\end{pmatrix}, \\
\begin{pmatrix}
1&2& & \\
2&1& & \\
 &1& & \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2&3& \\
2&1& & \\
 &1& & \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2&3& \\
2&1&2& \\
 &1& & \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2&3& \\
2&1&2& \\
3&1& & \\
 & & &
\end{pmatrix}, \\
\begin{pmatrix}
1&2&3& \\
2&1&2& \\
3&1&3& \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2& \\
3&1&3& \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3& \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
 & & &
\end{pmatrix}, \\
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4&5& &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4&5&6&
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4&5&6&7
\end{pmatrix}.
$$
We conclude that the answer is $7$. Retracing our steps, we highlight the following path in $B$, which corresponds to the longest increasing sequence in $A$ (accidentally, having exactly the same values):
$$
\begin{pmatrix}
1& & & \\
2& & & \\
3& & & \\
4&5&6&7
\end{pmatrix}.
$$

We can implement essentially the same solution in time $O(nm)$ using DFS. We go over the entries of $B$ in some arbitrary order, attempting to use the same recurrence formula we had before:
$$
B[ij] =
1 + \max_{\substack{i'j' \sim ij \\ A[i'j'] < A[ij]}} B[i'j'].
$$
If we are trying to access an entry $B[i'j']$ which hasn't already been computed we compute it recursively. Conversely, once an entry $B[ij]$ has been computed, there is no need to compute it again.

This can be implemented using the following pseudocode:

compute-B-matrix:
  initialize B to be empty
  for 1 <= i <= n and 1 <= j <= m:
     if B[i,j] is empty, call compute-entry(i,j)

compute-entry(i,j):
  let S = { neighbors (i',j') of (i,j) such that A[i',j'] < A[i,j] }
  if S is empty:
     set B[i,j] = 1
  if S is non-empty:
    for every (i',j') in S:
      if B[i',j'] is empty, call compute-entry(i',j')
    set B[i,j] = 1 + max({ B[i',j'] : (i',j') in S })

This solution essentially amounts to computing a topological ordering of a digraph naturally associated with $A$. Details left to the reader.


Master Theorem Case 3 Regularity Condition

If $f(n) = n\lg n$ then $f(n/b) = (n/b)\lg(n/b)$, and so $af(n/b) = a(n/b)\lg(n/b)$.


Multiple Knapsack using Dynamic Programming

When all values are 1 and all capacities the same, this is the bin-packing problem, which is Strongly NP-Complete. Therefore, a sensible DP solution is probably not possible unless P=NP.

For very small m, say m=3, you can do:

dp[item][capacity1][capacity2][capacity3] = max{
     value[item] + dp[item - 1][capacity1 - weight[item]][capacity2][capacity3],
     value[item] + dp[item - 1][capacity1][capacity2 - weight[item]][capacity3],
     value[item] + dp[item - 1][capacity1][capacity2][capacity3 - weight[item]],
     dp[item - 1][capacity1][capacity2][capacity3]}


Probability that a random hash from a universal family is injective

By definition, a family of hash functions $H$ with range of size $m$ is universal if for all $x \neq y$ in the domain of $H$,
$$
\Pr_{h \sim H} [h(x) = h(y)] \leq \frac{1}{m}.
$$
In your case, $m = N^2$. Let the $N$ elements in $S$ be $x_1,\ldots,x_N$. Using the union bound,
$$
\Pr_{h \sim H} [h(x_1),\ldots,h(x_N) \text{ not all distinct}] \leq
\sum_{1 \leq i < j \leq N} \Pr_{h \sim H}[h(x_i) = h(x_j)] \leq \frac{\binom{N}{2}}{N^2} \leq \frac{1}{2}.
$$
In other words, a random $h$ is successful with probability at least $1/2$. Therefore the expected number of times until a successful $h$ is chosen is at most $2$.


Your calculation is not right...
$$
U(R,C) = 2U(\frac{R}{2},C)\textrm{ or } 2U(R,\frac{C}{2})\\
U(1,1) = O(n)
$$

Basically, you have $N^2$ unique positions (which you drive your way down to recursively, rather than just looping) - for each of those you do a loop of O(N) so you have $O(N^3)$


Finding a graph-theoretic representation of expressions in Boole's algebra

A bit of shameless self-promotion, but you might find http://www.sciencedirect.com/science/article/pii/0895717794001669 relevant, as well as the earlier paper I cite there by Frank Harary.

Those papers present the idea that a boolean function can be represented as a hypercube in which the vertices represent combinations of truth values. That is, rather than construct a graph with a vertex for each boolean variable X, Y etc, construct a graph where one vertex represents the tuple <X=0,Y=0>, one represents <X=0,Y=1> etc.


I think the book you describe has a name. It is in seven volumes, only three and half  of which have been published. It is called The Art of Computer Programming,
(TAOCP) and is written by Donald Knuth.

It may be though that he will sometimes describe applications. But you can always skip that, and I doubt it makes much of the content. You should not be too disappointed with the maths.


How are statistics being applied in computer science to evaluate accuracy in research claims?

As a graduate student in computer science, who has exposure to research in fields other than computer science, and whose research group works in an area of computer science where statistics can be fruitfully applied, I can offer my experience; your mileage may vary.

In general, even the most well-meaning scientific research can fail to rigorously apply statistical analysis to results, and it is my experience that this does not always preclude papers including such poorly-analyzed results from being accepted for publication. The area in which my group operates is mainly in distributed computing and high-performance computer architecture. Often, research involves experimental designs the performance of which cannot easily be understood analytically in the required detail. As such, empirical results are often used as evidence for claims.

Clearly, experiments should be design - and results analyzed - in such a way as to provide some confidence that the results are statistically significant. Most of the time, this is not done, even in some of the most important venues. When statistical analysis is applied, it is almost never rigorous in any meaningful sense; the most one typically sees (and one is glad to see it!) is that an experiment was repeated n times, for some arbitrarily-chosen n, where typically $1 < n < 5$. The selection of error bars (if any are indicated) seems to be mainly a matter of personal preference or taste.

In summary, no, it's not just you; and it's not just software engineering. In general, based on my experience, several areas of computing research seem to err on the side of not doing enough. Indeed, it might be even be detrimental to the viability of a submitted paper to dwell on statistical considerations. That's not to say that I find the situation satisfactory; far from it. But these are my impressions. For instance, you may take a look at section 5 of this paper, which was presented at Supercomputing 2011, one of the most high-profile conferences in the area of high-performance computing. Specifically, take a look at some of the discussion of results in section 5, and see whether you arrive at the same conclusions that I do about the rigor of statistical analysis of experimental results.

More generally, this shortcoming may be symptomatic of a condition in some areas of computing to publish more papers rather than fewer, to target conferences rather than journals, and to emphasize incremental progress rather than significant and fundamental improvements in understanding. You might consult this article, which provides valuable insight along these lines.


Hint: There are seven satisfying assignments to the variables in each clause.


Algorithm for coherent motion. Which bus is app user on?

You basically have a table as follows:

Time | Person | Bus1 | Bus2 | ... | BusN  |
=====+========+======+======+=====+=======+
  0  | (x,y)  | (x,y)| (x,y)| ... | (x,y) |
  1  | (x,y)  | (x,y)| (x,y)| ... | (x,y) |
...

x,y being the coordinates of that Person/Bus at a specific point in time.

You then calculate the distance for each pair of Person/Bus and timepoint and map each Bus-Person-distance column to its rolling average of approx. 20 to 60 seconds (depends on precision and stuff like this).

You can then map the distances for each time-segment to a probability to be in a specific bus (if the location data quality is high, this should be pretty easy).

If you then plot the probabilities over time, for most times a specific bus should be on top. If this probability gets lower and another one rises, the person is likely changing the bus (or the buses are near each other).

PS: If your location API has methods for distance calculations, use those. If you have to do it yourself, there are some formulas to get from latitude and longitude to something for which the Euclidean distance ($D = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$) works (using that with latitude/longitude is wrong in general: see here.

PPS: I am not entirely sure, whether this problem is actually related to Computer Science.


Need help constructing a Deterministic Finite Automata with AT MOST

You can use states of the form $(i,j)$ where $i$ counts the number of 00s and $j$ counts the numbers of 11s read so far.


How do you convert bits into a different alphabet?

To estimate the number of decimal digits needed to represent a $128$ bit number you use logarithms to base $10$:
$128 \times \log_{10}(2) \approx 38.53$
so you need $39$ decimal digits to represent a $128$ bit number.
In a general, for an “alphabet” with $n$ symbols you need to find the value of $128 \times \log_n (2)$ and then round this up to the next whole number.


How to handle the time complexity for an optimization that depends on numerical values

One approach not mentioned above is parametrized complexity. The idea is to express the complexity of the algorithm with respect to a parameter of the input. A classical example is when the input is a graph and the parameter is the tree-width. But more generally, the parameter will be something that is typically not easily computable from the input. On a related note, the condition number can be seen as a particular case of parametrized complexity when dealing with numerical problems.


Amdahl's law is used to get an idea about where to optimize while considering parallelism.The theory of doing computational work in parallel has some fundamental laws that place limits on the benefits one can derive from parallelizing a computation. Amdahl's Law have detalied explanation of Amdahl's law and it's use.
Processor comes with some other resources like cache which can affect the performance. So if we add more processor, cache memory also increases. Each processor will get less data size to process that can fit into processor's cache which will increase the Performance(Superlinear speedup). But Amdahl's Law considers processors as the only resource but does not consider cache memory.


I came up with a way to modify Dijkstra's Algorithm to handle graphs with negative edge weighs

I'm afraid that this idea does not work (and I actually post this question as homework to my students, the reason being that at first glance it looks sound and complete).

Let $G(V, E)$ denote a graph with a cost function $c:e\in E\mapsto Z$, i.e., both positive and negative whole numbers, and no negative cycles. Let us assume there is an edge $e\langle v_i, v_j\rangle$ with a negative cost, i.e., $c(e_{ij}) <0$, so that $w_{min}=c(e_{ij})$.

Let $G'(V, E)$ denote a graph where the cost of each edge is now $c'(e_{ij})=c(e_{ij}) + w_{min}, \forall v_i, v_j\in V$. Certainly, there are no negative edge costs in $G'$.

Running Dijkstra on $G'$ to find the shortest path between two arbitrary vertices $s$ and $t$ would return a path $\pi:\langle s=v_0, v_1, v_2, ..., v_n=t\rangle$ with a cost equal to $\sum_{i=0}^{n-1}c'(e_{i, i+1})=\sum_{i=0}^{n-1}\left(c(e_{i,i+1})+w_{min}\right)=n\times w_{min}+\left(\sum_{i=0}^{n-1}c(e_{i, i+1})\right)$ ---please note the usage of $c'$ and $c$ in these expressions. In other words, the overall cost of paths in $G'$ penalizes larger paths by the constant $w_{min}$ and in the end, it might very easily return a different path.

It does not matter whether you correct now the cost of the path returned by running Dijkstra in $G'$, as it might be simply different.

Hope this helps,


What is the optimal strategy for filtering a large collection of items with multiple filter functions?

Independent filters

If the filters are independent, a greedy algorithm can be used to find the optimal order.  Sort the filters by increasing value of $t/p$, where $t$ is the time to run the filter and $p$ is the fraction of items that are filtered out by the filter.  This gives the optimal order.

To give some intuition for why this might be a plausible answer: ideally, we'd prefer filters that take less time; and ideally, we'd prefer filters that filter out a higher fraction of items.  Intuitively, you can see how $t/p$ somehow incorporates both of those.

A formal proof of optimality involves an exchange argument.  I won't detail the proof here, as it can be derived easily using standard techniques.  For a detailed writeup of the proof, see Determine what is the best order for running filters on a dataset.

Correlated filters

If there can be correlations between the filters (i.e., they are not independent), the optimal order cannot be determined from the information provided without knowledge of the correlations.

Here's an example, based on making a small modification to your example.  Suppose we have two filters, filter A and filter B.  Suppose filter A runs in 4.5ms and filters out 50% on average; filter B runs in 1ms and filters out 25% on average.  Also suppose that anything filtered out by filter B is also filtered out by filter A.  Then the optimal order is to just do filter A.  Your formulas give A,B: $4.5+0.5 \times 1 = 5.0$ and B,A: $1 + 0.75 \times 4.5 = 4.375$, so your formulas might make B,A look like the best choice -- but in fact just doing A alone is even better.

Unfortunately, in practice I would expect that filters might often be correlated.  To deal with this, you'd need to know some information about the correlation structure.  If you don't have any information on the correlation structure, one possible approach is to use the greedy strategy, recognizing that it might not be optimal for your particular situation.  Another possible approach is to gather data on the correlation structure and then use that additional information to try to find a better order, though this may not admit as clean of an answer.


NP-complete reduction for a k-dumbbell graph

Hint: Following your idea, you want to reduce the clique problem to the dumbbell problem, to show that the latter is NP-hard. Given an instance $(G,k)$ of the clique problem, it is natural to consider two copies $G',G''$ of your original graph, connected in some way, so that if the original graphs contains a $k$-clique, then the new one contains a $k$-dumbbell.

If the new graph contains a $k$-dumbbell restricted to one of the copies, then the original graph certainly contains a $k$-clique. You want to arrange matters so that if the $k$-dumbbell straddles both copies, then it is composed of a $k$-clique in each one.

This is just a hint, so I'm not giving a full solution. Indeed, there might be several ways of using this idea to get an NP-hardness reduction. Some of them require you to slightly change the value of $k$ from the clique instance to the dumbbell instance.


Is there a name for this relation on CFGs?

This is a kind of (surjective) homomorphism,  but the traditional definition is defined only over terminal symbols, not nonterminals.

Your definition would merge unrelated nonterminals from the first grammar with each other in the second grammar, thereby allowing (the image of) unrelated parts of the grammar to get mixed up with each other. This probably does not have nice properties, at least compared to the traditional definition of homomorphism.

That said, I can imagine that it is useful for some kinds of modelling, of AOP, of dynamic binding, of extensible grammars. I'd be interested in knowing what your application is.


This is known as counting sort. On a domain of size $d$, counting sort runs in time $O(dn)$, compared to $O(n\log n)$ of comparison-based sorts. When $d\ll\log n$, i.e., when the domain is small compared to the total number of elements, we would expect counting sort to be faster. Counting sort can even be iterated, and this is known as radix sort.

If $d = o(\log n)$, then counting sort runs in time $o(n\log n)$, which might seem to contradict the well-known $\Omega(n\log n)$ lower bound on sorting. There is no contradiction, however, since the lower bound only holds for comparison-based sorts, which counting sort evidently isn't.


Could program verification techniques prevent bugs of the genre of Heartbleed from occurring?

To answer your question in the most concise way - yes, this bug could have potentially been caught by formal verification tools. Indeed, the property "never send a block which is bigger than the size of the hearbeat that was sent" is fairly simple to formalize in most specification languages (e.g. LTL).

The problem (which is a common criticism against formal methods) is that the specifications you use are written by humans. Indeed, formal methods only shift the bug-hunting challenge from finding the bugs to defining what bugs are. This is a difficult task.

Also, formally verifying software is notoriously difficult due to the state-explosion problem. In this case, it is especially relevant, since many times in order to avoid the state explosion, we abstract away bounds. For example, when we want to say "every request is followed by a grant, within 100000 steps", we need a very long formula, so we abstract it to the formula "every request is eventually followed by a grant".

Thus, in the heartbleed case, even while attempting to formalize the requirements, the bound in question could have been abstracted away, resulting in the same behavior.

To sum up, potentially this bug could have been avoided by using formal methods, but there would have had to be a human specifying this property in advance.