Given price and number of pages of each book, What is the maximum number of pages you can buy? You are in a book shop which sells n different books. You know the price and number of pages of each book.

You have decided that the total price of your purchases will be at most x. What is the maximum number of pages you can buy? You can buy each book at most once.

Example:

In:
4 10
4 8 5 3  //price
5 12 8 1 //pages
Out:
13
Explaination: You can buy books 1 and 3. Their price is 4+5=9 and the number of pages is 5+8=13

This is my recursive approach :

f(i,j) is max pages, when you can afford i units of money and j is the index in vector uptill the jth book. ie 0 to jth books are considered.

f(x, 0)=max( f(x-price[indx], indx+1) + pages[indx], f(x,indx+1) );

I am having difficulty making the base case, what should be the base case?

Thank you.

I am afraid that the following recurrence equation as in the question is incorrect.

f(x, 0) = max( f(x-price[indx], indx+1) + pages[indx], f(x,indx+1) )

Let g(i,j) be the maximum number of pages possible when you have i units of money to spare and books 0..j available to select, where 0..j means 0, 1, ..., and j. (I use g instead of f since I am not absolutely sure of the definition of f in the question. It looks like g(i,j) should be the same as f(i,j) in the question. )

Here is the recurrence equation.

g(x, indx+1) = ( x >= price[indx+1] ) ?
              max( g(x - price[indx+1], indx) + pages[indx+1], g(x,indx) ) :
              g(x, indx)

In plain words, there are (at most) two possibilities when books 0..(indx+1) are available to select.

Book indx+1 is selected (when x >= price[indx+1]). You have pages[indx+1] more pages.

Then you are left with x - price[indx+1] units of money and books 0..indx to select.
Otherwise.

Then you are left with x units of money and books 0..indx to select.

Note that the available books on the right-hand side of the equation are always less than the available books on the left-hand side. That reduction of a larger problem to a smaller problem signifies the power of recursion.

The base case are when no books are available, i.e., g(i,0) = 0 for all i, and when there is no money to spare, i.e., g(0, j) = 0 for all j.


Solving $\text{key}=(\sum_{K=0}^n\frac{1}{a^K})\bmod m$ with High limits I was solving this equation:
$$\text{key}=\left(\sum_{K=0}^n\frac{1}{a^K}\right)\bmod{m}.$$
Given
$$ 1,000,000,000 < a, n, m \; < 5,000,000,000, $$
$$ a, m \text{ are coprime}. $$
I solved it by brute force, but it won't work in the given constrains so I need a faster algorithm or is there is something I can notice to make the formula easier to solve ?

Solve a linear homogeneous recurrence to obtain the identity $$\sum_{K=0}^n\frac1{a^K}=\begin{cases}\frac{1-1/a^{n+1}}{1-1/a}&\text{if }a\neq1\pmod m\\n+1&\text{if }a=1\pmod m\end{cases}$$ and use efficient algorithms for multiplicative inversion and exponentiation mod $m$.


From the LR(1) parsing table, can we deduce that it is also an LALR and SLR table? There is this question I read somewhere but could not answer myself.

Assume I have an LR(1) Parsing table. Is there any way that just by looking at it and its items, can I deduce that it is also a table for LALR and SLR?

Trivially, yes: the grammar is extractible from the items.

Probably more in the spirit of the question. LALR(1) is easily extracted from LR(1): merge LR(1) items which correspond to the same LR(0) one and the grammar isn't LALR(1) if that process results in conflicts. (BTW this can be considered as a definition of LALR(1)).

SLR(1) is not so easy; you need to compute the follow sets to find out if there are conflicts. (SLR(1) is based on the LR(0) items like LALR(1), but it has "unneeded" conflicts due to the use of follow sets instead of the computation of look ahead one to choose which production to reduce.)


totally ordered semigroups Given a semigroup is it possible to give a total order to it?

If not possible in the general case then what about the case of finitely generated finite semigroups?

Does there exist a natural extension of the syntactic order given to a semigroup w.r.t. an upper set? (currently it only induces a partial order)

Monogenic semigroups.
Consider the case of a [monogenic semigroup](monogenic semigroup), that is, a semigroup $S$ generated by a single element $s$. If $S$ is finite, then it can be totally ordered if and only if it is aperiodic, that is, if there exists a positive integer n such that $s^n = s^{n + 1}$. In this case, the order could be $s \leqslant s^2 \leqslant \dotsm \leqslant s^n$.
If $S$ is not aperiodic, then it contains a finite subgroup, and the only compatible order on a finite group is the equality, as you observed.

If $S$ is infinite, it can also be ordered by $s \leqslant s^2 \leqslant s^3 \leqslant\dotsm $.

Arbitrary semigroups. An interesting example is the free monoid $A^*$ equipped with some shortlex order. Shortlex orders are total and are compatible with the concatenation product.

Second question. I am not sure what you mean by a "finitely generated finite semigroup" since every finite semigroup is finitely generated. Thus I suppose that the question is whether the order of a finite ordered semigroup can be a total order. There are some examples which are not monogenic, for instance the ordered semigroup $(S, \leqslant)$ with $S = \{a,b\}$, $a \leqslant b$,  $aa = ba = a$ and $ab = bb = b$.

Third question. See my comment.


FLP Impossiblity Result assumption of $C_1 = e'(C_0)$ FLP86's famous proof regarding impossibility of async distributed processes with a single fault assumes in the proof of the third lemma the existence of an event $e'$ such that the neighbor configurations $C_0$ and $C_1$ can be related as

$C_1 = e'(C_0)$.

I don't get how this is possible, as it seems to me like $e'$ carries out a state transition from a 0-valent configuration to a 1-valent configuration. In addition to this being counter intuitive the proof of case 1 of lemma 3 clearly states that any successor of a 0-valent configuration has to be a 0-valent configuration. What am I missing here?

At least in this part of the article, the character C is used for bivalent configurations. The index $0$ for the bivalent $C_0$ was chosen simply because $e(C_0)$ is 0-valent and the index $1$ in $C_1$ was chosen because $e(C_1)$ is 1-valent, even though $C_0$ and $C_1$ are bivalent neighbors (when applying $e'$).


$O(n \log n)$ simple polygon triangulation via divide and conquer I am looking for the simplest possible $O(n \log n)$ algorithm for triangulating a simple polygon.  It seems like there should be a simple divide and conquer variant that would fit the bill, ideally one avoiding auxiliary data structures such as trapezoidal decompositions.  Indeed, all that would be required is an $O(n)$ algorithm for finding a roughly balanced diagonal.  However, I am unable to find any algorithms that are as simple as I (perhaps naively) imagine should exist; nearly all the research is focused on $o(n \log n)$ algorithms, nearly all of which operate via trapezoidal decomposition.

Garey, Johnson, Preparata and Tarjan came up with a simple $O(n\log n)$ algorithm back in 1978. It is described in many lecture notes, for example these lecture notes of Piotr Indyk.


Community detection in weighted directed graphs for fixed number of communities I have a weighted directed graph $G=(V,E)$ with positive weights. Say these vertices represent cities and the weight $w : V_1 \rightarrow V_2$ represents number of students moving into other cities for college. Note here that a city $A$ may have a small population and it may be sending a major proportion of it's outgoing students to another city $B$. If the converse holds true for city $B$, in that, most of it's incoming students come from city $A$ as a proportion of the entire incoming population, we say the weight of the edge connecting city $A$ to city $B$ should be high. So one can think of formalizing the above as a function of $\% inflow$ and $\% outflow$ problem. Now an algorithm like Gervin-Newman algorithm will find communities in such a graph. Here the number of communities detected increases over the number of cities considered. Is there a community detection algorithm for weighted directed graphs where I can pre-specify the number of communities I will be looking to get as output.

There are lots of community detection algorithms that need the number of communities as input. For example, Bigclam [1], a matrix factorization approach, needs the number of communities as input. Another example is the seed expansion [2] method that needs the number of communities as input. I'm sure there are many algorithms that take the number of communities as input, but you need to do some research and find the one that is best suitable for you. Looking at these algorithms may be a good start.

You may also think about your own community detection algorithm specific  to your problem. For example, you can use seed expansion and start with $k$ seeds (cities) and try to expand those seeds whenever appropriate (appropriate is a vague word, you need some calculations to see if an expansion is appropriate or not).

[1] Yang, Jaewon, and Jure Leskovec. "Overlapping community detection at scale: a nonnegative matrix factorization approach." Proceedings of the sixth ACM international conference on Web search and data mining. ACM, 2013.

[2] Whang, Joyce Jiyoung, David F. Gleich, and Inderjit S. Dhillon. "Overlapping community detection using seed set expansion." Proceedings of the 22nd ACM international conference on Conference on information & knowledge management. ACM, 2013.


Is Dijkstras algorithm used in modern route-finding systems? Is Dijkstra's algorithm used in modern route-finding systems such as Google maps or the satnav in your car? If not, then what is?

Google Maps in 2009 used Contraction Hierarchies - see this tech talk.

Since then, some mind-blowing methods have been discovered, capable of doing cross-country routing in fractional milliseconds - the so-called "two-hop labeling distance oracles". See here, or search for "Hub labeling" or "Shortest paths for the masses". I think I heard Bing uses this one. It also has applications like the ability to find the nearest point of interest (e.g. nearest gas station) with a complexity independent on the number of gas stations.


Amortized analysis - adding operations to a data structure One of the finer points of amortized analysis about which I have been able to find relatively little information is the broad question of what happens to the amortized cost of a structure's existing operations if we add a new one. I'll use two popular examples to illustrate my confusion:
In a binary counter which only supports the increment operation, choosing the potential function $\Phi=\#$ of $1$'s in the present configuration gives us constant amortized cost for the operation. In every example I can see in the literature, adding the decrement operation to the counter creates a situation where both it and the increment operation have linear amortized costs. The argument given is that we can toggle $m$ times between values of $2^n$ and $2^n-1$ with a series of alternating decrement and increment operations, giving us a time of $\Theta(mn)$.
In a binomial heap, using the number of binomial trees in the structure as a potential function gives us constant amortized time for insertion. Popping the minimum takes logarithmic time both amortized and in actuality.
Perhaps I'm mistaken, but I see a certain contradiction here. In a binomial heap we could reach a point where we have one large binomial tree with $2^n$ elements and repeatedly perform pop and push operations, which will cost $\Theta(m\log n)$ time. Even if each vertex keeps its children in a linked list which would give the deletions constant time, the insertions will all take logarithmic time.
Having said that, the insertion operations for both structures still function the same way: for any sufficiently large $m$, any series of $m$ insertions to either structure still takes $O(m)$ time - the inclusion of the deletion (decrement in the counter) operation doesn't affect the way the insertion operation works.
So why do we say that adding decrementation to a binary counter increases the amortized cost for incrementation and then ignore the same argument when analyzing binomial heaps?

I don't know much about the amortized running time of binomial heap, but after reading Wikipedia, I suspect the following might be true: the amortized time of a long sequence of consecutive insert operations is $O(1)$; but this is only true for consecutive insert operations that don't have any other operations mixed in.  Based on that, I wouldn't really summarize the running time of a binomial heap by saying that insert takes $O(1)$ amortized time, without further caveats.
As you quite astutely point out with your example based on a binary counter, the amortized running time of an operation depends on the full set of operations that are allowed to be performed.  So I suspect that the resolution is that the claim about the amortized running time of inserts into a binomial heap wasn't quite right, or had some additional caveats.  I don't know that for sure, as I don't know much about binomial heaps, but that would be my running hypothesis at this stage.


Jobs in algorithm design I just wanted to know if there are actually jobs only devoted to creating and optimising algorithms after finishing a Bachelors degree. Or is it only restricted to PhD's?

I solve problems on SPOJ and CodeForces, but I'm not sure if I'd get a job doing something like that.

I think it would be unusual to find an organisation advertising specifically for someone to design algorithms. Generally speaking a company will have a product or a number of products which go through an improvement and release cycle. Part of this will involve optimising algorithms/code. However to specialise so greatly I would have thought would mean such an employee would spend much of their time twiddling their thumbs! Any organisation nowadays generally wants someone to be multi-skilled (eg able to code as well)

Having said that, large organisations which engage in a lot of research (the likes of NASA, Google, Facebook, Bell Labs, Xerox of old) may have posts such as that. Bear in mind that those guys will be looking for real genius-level staff as well. (You may well be a genius.. :) )

I would try to broaden my horizons a little beyond just algos though, as after all, an algorithm is no good unless it can be implemented! And that will always bring its own set of challenges given available resources and the specific nature of the problem domain.

I know this isn't an "answer" just my thoughts. As a first port of call try typing "algorithm designer" into monster.com or similar job site! Good luck!


Mathematical optimization with thresholded optimization function Gradient descent can be used to minimize an objective function $\Phi:\mathbb{R}^d \to \mathbb{R}$, if we know how to evaluate $\Phi$ on any input of our choice.

However, my situation is a little different.  I have an objective function $\Phi$ of the form

$$\Phi(x) = \Phi_1(x) + \Phi_2(x),$$

where I can evaluate $\Phi_1$ on any input of my choice, but I don't have the ability to do that for $\Phi_2$.  Instead, for $\Phi_2$, I have only a thresholded (quantized) version of $\Phi_2$: I can evaluate $f_2:\mathbb{R}^d \to \{0,1\}$ on any input of my choice, where $f_2$ is defined by

$$f_2(x) = \begin{cases}
0 &\text{if } \Phi_2(x)\le t\\
1 &\text{if } \Phi_2(x) > t\\
\end{cases}$$

and $t$ is fixed.  You can assume that $\Phi_2$ is smooth and has all the nice properties you might like, but I can only evaluate $f_2$, not $\Phi_2$.  How can I search for an $x$ that's likely to make $\Phi(x)$ as small as possible, in this situation?  Is there any way to adapt gradient descent or other mathematical optimization method to this setting?

Why I think there might be some hope: if we find $x',\delta \in \mathbb{R}^d$ such that $f(x')=0$ and $f(x'+\delta)=1$, where $x' \approx x$ and $\delta \approx 0$, then we've learned some information about $\Phi_2$, e.g., that the partial derivative of $\Phi_2$ is likely to be large in the $\delta$ direction.  It seems like it might be possible to build an algorithm to exploit this kind of information.  Are there any techniques to handle this kind of situation?

I guess $f_2(x)$ is some sort of oracle that tells you if $\Phi_2(x)$ is greater than $t$?  If the set $\{\mathbf{x} : \Phi_2(x) \le t\}$ is convex, then I think projected gradient algorithm might be helpful. Could you provide more information on $\Phi_2(x)$? The question is kinda confusing with the information provided.


parallelizing $k$-means I'm having trouble thinking about the following. If we have two machines 1 and 2 that evenly split a set of data points, does $k$-means separately, then averages the result, does this agree with just $k$-means on one machine?

To be more specific, consider the following routine:

  Split an input dataset evenly between 1 and 2.
  Initialize $k$ centroids that are the same on both 1 and 2.
  Use $k$-means algorithm to find updated centroids.
  Find a new set of $k$ centroids by averaging the corresponding centroid from 1 and 2.
  Loop over 2.

Will this agree with just running $k$-means? I think that it is the averaging part that might work, but then I'm not sure if this routine finishes running.

Short answer is yes, you can parallelize $k$-means, essentially as you described.

First, on each processor, you assign points to the centroids closest to them. This part is trivial as long as each processor knows the locations of the centroids.

Next, you compute the new location of the centroids on each processor, and then combine them.
But as Raphael pointed out in his comment, you have to weight the centroids from machine 1 and machine 2.

Let's consider a simple example, and only look at 5 points assigned to one of the centroids $C$. Suppose that machine 1 has points $x_1$ and $x_2$ and machine 2 has points $x_3, x_4$ and $x_5$. If we were dealing with the standard (single processor) version of $k$-means, then the new location of $C$ would be
$$
C' = \frac{1}{5} \sum_{i=1}^5 x_i
$$

The contribution from machine 1 is
$$C_1 = \frac{1}{2} \sum_{i=1}^2 x_i$$

and the contribution from machine 2 is
$$
C_2 = \frac{1}{3} \sum_{i=3}^5 x_i
$$

In order to properly combine the results from the two machines, you just do the algebra:
$$
C' = \frac{1}{5}(2C_1 + 3C_2)
$$

Your stopping condition should be the same as in the standard version of $k$-means.


What are "state registers" and "code registers"? While reading a chapter about FSM, I was stuck on the following slide:

In fact, I have been unable to determine what are "state registers" and "code registers", which were not explained in the course. Therefore, I have used  to search for the definitions on the net, but I haven't yet found any result.

While I've not heard those exact terms, my guess would be that "code registers" are the registers that code you would write set. For example, on an Intel x86 platform, that would be the general purpose registers like the AX, BX, CX, etc. and EAX, EBX, ECX, etc. registers. These are registers that you can either use directly if you're writing assembly code, or that are used by the code generated by your compiler.

Meanwhile, the computer also has a set of registers for its own use. Things like the program counter (or instruction pointer) register which points to the next instruction to execute in memory. They can also indicate statuses; things like carry registers that indicate whether there was a carry out of an addition between 2 other registers. (For example if you add 1 to MAX_INT, you'll generate a 1-bit carry that the registers can't hold.)

Each processor is different. The 6502 had 2 registers (labeled X and Y) and an accumulator as general purpose (or code) registers. Then it has one status register that held 7 bits of status flags, a stack pointer, and a program counter, which would be "state registers".


How could i create a multi-threading system in a kernel? Im trying to figure out if there's an assembler instructions or a bios intruction to get multi-threading in a kernel. In the case that doesn't exist that, how could i set muti-threading in a kernel?

In a multiprocessing system the other cores of the CPU are initiated with boot code like UEFI or legacy bootloader just like the first core of the computer.
The CPU is manufactured to use a "core 0" as the first core of the system. After boot, the kernel needs to use the Local APIC of core 0 to send IPI ( interprocessor interrupts) to other cores to start them. As stated on osdev.org,
IPIs are sent through the BSP's LAPIC. Find the LAPIC base address from the MP tables or ACPI tables, then you can write 32-bit words to base + 0x300 and base + 0x310 to send IPIs. For a init IPI or startup IPI, you must first write the target LAPIC ID into bits 24-27 of base + 0x310. Then, for an init IPI, write 0x00004500 to base + 0x300. For a SIPI, write 0x00004600, ored with the page number at which you want to AP to start executing, to base + 0x300. For more information, see http://wiki.osdev.org/APIC#Local_APIC_registers.


Proving that an equal partition does not exist We are given a set of $n$ numbers and want to know whether it can be partitioned to two sets with an equal sum.

To prove that an equal partition exists, it is sufficient to show a partition.

What is the shortest way to prove that an equal partition does NOT exist?
Apparently the only way to prove it is to show all the partitions and show that they are not equal. Is there a shorter proof?

The current expectation is that most likely there is no efficient (polynomial-size, polynomially-verifiable) way to do that.

The partition problem is NP-complete.  For a NP-complete problem, we have an efficient way to certify that the answer to the question is YES, but not necessarily any efficient way to certify that the answer is NO.  If you find an efficient way to verify that the answer is NO (i.e., a polynomial-length proof that can be verified in polynomial time), then you have proven that the problem is in co-NP.  If you prove that any NP-complete problem is in co-NP, then you have proven NP = co-NP.  Currently, it is widely conjectured that NP $\ne$ co-NP.  Assuming that conjecture is correct, there is no polynomial-length polynomially-verifiable proof that an equal partition does not exist.


Difference between Turing machine end state and halt Is there a difference between the end state of a Turing machine and the halt state? Especially, for example the Busy Beaver 3. It is said that it is with 3 states but there is also a halt. Is the end state $q_2$ or the $halt$?

"End(ing) state" and "halt(ing) state" are just two (four) different ways of saying the same thing.


Can other models of computation equivalent to Turing machines also recognize the same languages? There are other models of computation equivalent to Turing machines in terms of computability.

Turing machines also recognize recursively enumerable languages.

My questions are

Do other models of computation equivalent to Turing machines also recognize the same languages?
Are computability and language recognization unrelated to each other, so that other models of computation equivalent to Turing machines don't recognize or accept any language?

Thanks.

Two models of computation are equivalent iff they can compute exactly the same set of functions. So the answer to your question is yes, they can recognize the same languages. The definition of "accept" has to be altered a bit to fit the new model, of course, since for example in the lambda calculus you have no states that you could mark as accepting.


How to describe the time complexity of a continually running program with a stream of inputs? Maybe time complexity isn't the right term.   Performance?   There must be some way of describing the efficiency of a program over time.

For instance, I recently had a part of a program that took a continual stream of discrete strings (~256 chars) and checked if each one was in some sort of set or container.

Initially I was using a hash set, though I found despite the O(1) of looking up in the set, computing of the hash of the strings was slower than using a tree instead of a hashset and not computing any hashes.

How would one compare these two operations?

k = key length (smallish, 256)
n = items in the collection  (~10)
m = number of keys streamed (-> infinity)

hash set/table lookup:
worst:  O(m * (k + n)) -> O(m)
best:   O(m * k) -> O(m)

tree lookup:
worst:  O(m * k)  ->  O(m)
best:  O(m)

Usually, in practice, the tree will destroy the hash set.   The last time I had to write something like this, the tree lookup was about 5x faster.

I would say that you should not look at the overall runtime (as it will be dominated by $m =\infty$ anyway) and instead look at the expected complexity of processing a single element (or a group of them if it doesn't scale linearly).

I'm not entirely sure what you mean with "Tree lookup" but I will just guess and provide an answer for that:

Calculating the hash of a key with length $k$ is done in $\mathcal O(k)$.
The corresponding field in the hashmap/table/set is then retrieved with a single lookup.

Assuming your tree is a BST where each node is a key (256 chars, alphabet of size 26) and you compare either left or right side and you have 10 nodes in the tree:

The tree has $log_2(10) \approx 4$ levels (1,2,4,2 nodes)
For a lookup, in each level the current key has to be compared to the node's key. The chance that the first characters match is $\frac1{26}$. That the first two match $\frac1{26^2}$, and so on.
In most cases, you will have a mismatch at the all four nodes where a value is compared
Your average case thus involves a few (2-4) lookups (following left or right child pointers in the tree) and comparing a few letters. If the key matches, the whole key is compared but I assume that this doesn't happen very often.

Thus, the BST lookup has a better performance without further modifications.

Maybe more fitting for stackoverflow than cs.stackexchange but still, my suggestion for your problem would be the following:

Determine if the values in the collection have some pattern (if they are SHA hashes of random data or similar, very very likely not the case)
Look at the percentage of successful matches (I would guess very low)
Implement a custom "Hashing". If the items in your collections start with different letters (or 2, whatever), you only need the first letter of each element in your stream to know with which item from your collection you have to compare it (for equality).


Is there another common name for dominating set in graphs? I am looking for graphs which the value of a minimum dominating set is known (Where can I find a data set of graphs with known domination numbers?). So far I have not found anything, so perhaps I missed a search term. Does anybody know if dominating set goes by some other name?

No, dominating set is a common name, and I've never seen another name for the definition. You might get luckier if you search for domination number though, that's the size of a minimum dominating set.


Randomized and deterministic reduction Given a problem $X$, to show it is is $\sf NP$-complete, one usually shows a deterministic reduction from an $\sf NP$-complete problem.

If it is hard to show deterministic reduction, then one shows a randomized reduction.

What does a deterministic reduction give about the hardness of the problem that a randomized reduction does not give?
What is the consequence if there is a randomized reduction from an $\sf NP$-complete to $X$, however one can show there is no deterministic reduction from an $\sf NP$-complete problem to $X$?
If we have only randomized reduction, is $X$ still an $\sf NP$-complete problem or could it have faster algorithms?
What does it mean for problem $X$ if there is a randomized reduction from $\sf NP$-complete problems? (Does it mean $X$ is still $\sf NP$-complete?)

Let's answer your questions one by one:

A deterministic reduction proves NP-hardness. A randomized reduction doesn't. If a problem is NP-hard with respect to randomized reductions, then it could (potentially) be solvable in polynomial time even if P$\neq$NP. The assumption BPP$\neq$NP does rule out polynomial time algorithms for any such problem, however – even randomized ones.
The consequence is that P$\neq$BPP, which is conjectured to be false.
NP-hardness is defined with respect to deterministic reductions.
We say that the problem is "NP-hard with respect to randomized reductions".


Complexity class of an algorithm What is the complexity class of an algorithm that runs in $n^{\mathcal{O}(\sqrt{n}log(n))}$ time?

As $n$ gets large $\sqrt{n}log(n)$ increases at a very slow rate. Does this mean that the algorithm has the same complexity as $n^{\mathcal{O}(1)}$, which would be in $P$?

No, $\sqrt{n}$ increases far faster than $O(1)$, and $n^{\sqrt{n}}$ grows far faster than $n^{O(1)}$.  No, it certainly does not have the same runtime.  See Sorting functions by asymptotic growth.

There may be no predefined complexity class; the complexity class is the class of all algorithms who run in time $n^{O(\sqrt{n} \log n)}$, and there's probably not much more to say.


How to find the cost of pseudocode with a nested loop and a nested if statement? How can I find the cost of pseudocode with a nested loop and a nested if statement?

On the left hand side is an example from a textbook I am following. On the right hand side is pseudo code that I found. I took a guess, but I don't know what the time would be for the inner code fragments.

I am especially unsure what the code segments inside the if statement would be because the if statement doesn't always occur.

Big O analysis

The answer is O(n^2).

Good strategy for working this out is eliminate all constant time operations (unless it is a return / break that will change the loop), as everything will always be at least O(1).

This means you can eliminate everything inside the if, as well as the if. So you are left with a simple nested loop running over n

Hence O(n^2)

Cost analysis

You always assume worst case (unless explicitly told otherwise). Therefore assume if statement will be true and statements will run every loop (as there can exist a sorting order where this is true), so your statements will have the same cost as your loop


Complexity of closest set of points in plane problem Given a set of points on a plane find the set of $n$ points that are closest to the origin.  (Points are pairs of integers.)

  Input: list of points.
  Initialize a priority queue $Q$, where priority is measured according to the distance from origin (larger distance is higher priority).
  For each point $p$:

  Add $p$ to $Q$.
  If $Q$ contains $n+1$ points, remove the point with highest priority.

  Return $Q$.

The priority queue is implemented using a heap.

I'm thinking the runtime is $O(n + k \log n)$, and space is $O(n + m)$.  Where $n$ is the number of points examined, $m$ is the number of points being returned and $k$ is $\max(0, n - m)$.  Space is both the priority queue and the output.

My understanding is that a heap can be constructed in $O(n)$ hence the $O(n)$ in the runtime complexity.  I find it hard to reason why heap construction, which has an upper bound $O(n \log n)$ can be reduced to $O(n)$, but $k$ deletions should be $O(k \log n)$.

I might be overthinking this, but thought I would ask.

There seems to be some confusion regarding parameters. There is $n$, which is the number of points we wish to return; and there is another parameter, let's say $N$, which is the number of points in the input. Assuming that $N \geq n$, the output would consist of $n$ points, so we can dispense with your $k$.

Since the heap contains at most $n$ points, all operations take $O(\log n)$ time. Therefore the running time can be upper-bounded by $O(N\log n)$. It should be easy to construct matching hard instances which show that the worst-case time complexity is indeed $\Theta(N\log n)$.

Regarding space consumption, the usual convention is to measure only the "work tape", that is, only the auxiliary space taken by the procedure, without the input and output. In this case, this is only the heap, which uses up $\Theta(n)$ space.


How to find the virtual pages and physical memory frames? So i am given a system of 20 bits virtual addresses and 18 bits physical addresses using paging with pages size 4Kbytes.
I am told to find the maximum number of virtual pages that a process can have and the maximum number of physical memory frames the system can have.

So 2^12 page size makes 12 bits for offset and 8 bits for page number right?
and 2^8 is 256 is the maximum virtual pages that a process can have? Correct me if im wrong.

And for the second one im having kind of trouble.
Ive seen a post about a similar question but didn't really understand it.
Is it 2^18 bits for physical address multiplying it with the page size like
(2^18)*4096 to get the maximum physical memory frames?

Also a last part gives me the following:

00110110011110111100

and says the virtual page containing the address is mapped onto physical frame 45, give the corresponding physical address in binary format.
How do i find that?

So 2^12 page size makes 12 bits for offset and 8 bits for page number right? and 2^8 is 256 is the maximum virtual pages that a process can have? Correct me if im wrong.

you are correct

  maximum number of physical memory frames the system can have.

the size of frames is the same as the size of pages

so you have 18 bit for physical memory, which 12 bit of that is needed for the offset, now you are left with 6 bit which means you can have $2^6$ frames.

  Also a last part gives me the following:

  00110110011110111100

  and says the virtual page containing the address is mapped onto
  physical frame 45, give the corresponding physical address in binary
  format. How do i find that?

00110110 011110111100

so the 12 bits from the right are for the offset which you dont need to change, the remaining 8 bit which is 00110110 needs to be replaced with 45 and instead of 8 bit we would use 6 bit to map into physical address

therefore the physical address would be 101101 011110111100

this means that in the 54th row (00110110) of our page table for that process we would find the corresponding frame for that page to be 45 (101101)


Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive I read somewhere that if a grammar is left recursive as well as right recursive, then it is not necessarily ambiguous.

I couldn't make up my mind on this statement. How can a grammar which is both left recursive as well as right recursive not have more than one parse tree for a single string.

Am I right? If not, please provide a counter example whereby my assumption can be proved wrong.

Thanks in advance!

Do you mean a grammar with left and right recursive rules, or a single production rule with left and right recursive alternatives?

If a single production rule is both left and right recursive, the grammar is ambiguous. For example, the following rule

$A \to \alpha A \mid A \alpha$

has the following two (left-most) derivations:

$A \Rightarrow \alpha A \Rightarrow \alpha A \alpha $ corresponding to the grouping $(\alpha (A\alpha)$

$A \Rightarrow A \alpha \Rightarrow \alpha A \alpha $ corresponding to the grouping
$((\alpha A) \alpha)$

But a grammar can have left recursive and right recursive rules in different production rules and that can be unambiguous. For example, the following grammar:

$\begin{align*}
  S &\to X \mid Y \\
  X &\to X b \\
  Y &\to a Y \\
 \end{align*}$

In this grammar, $X$ and $Y$ are left and right recursive, respectively, but the grammar is unambiguous.


Complexity for checking if an array is a min-d-heap The problem is this: Let us have an int array of length n. Find an algorithm to determine if the array represents a min-d-heap.

My solution: We start from the first index in the array, and compare its value to the value of its children (all the nodes at locations $i*d+k$ where $k \in \{1,2,...d\}$, assuming we start the array at index 0). We do it for every index until we reach an index that "has no children", meaning $i*d+1>n-1$. If at every point the value of the parent's key was lower than the value of all of its children' keys we return $True$, meaning the array represents a min-d-heap.

Now - my problem is calculating the time complexity for this algorithm:

I have managed to prove that if we look at a "complete" d-tree, we get a time complexity of $O(n)$ worst case. This is my proof:

Let us assume the tree is of height $h$. We note that at the last level we have $d^{h-1}$ items. Now, we can show that the tree excluding the last level has $O(\frac{n}{d})$ items: $$\frac{\sum_{i=0}^{h-1}d^i}{d^{h-1}} = \frac{d^{h-1}-1}{(d-1)d^{h-1}} = O(\frac{1}{d})$$
Therefore, for every node excluding the last level we make $d$ comparisons, and we get that the time complexity for the algorithm is $O(d*\frac{n}{d}) = O(n)$.

My problem is that my proof was based on the fact that we have  a complete tree. There are cases which are asymmetric and I found harder to prove for the general case. I did check it by hand and showed that it is indeed the same time complexity but couldn't prove it.

Would like your help in the last part, Thanks!

Apart from the answer given by rici in the comment to the question, I've come up today with an answer to prove this exact algorithm's time complexity, and it's pretty simple:

Since the algorithm goes over all of the parents in the heap (i.e all the nodes that have children), we only need to look at them while calculating the time complexity. The first parent is obviously the first item in the array. The last parent, is the parent of the last item in the array. The last item in the array is located at index $n-1$, therefore the parent of the last item (and the last parent) is located at index $\lfloor\frac{n-2}{d}\rfloor$ which is $O(\frac{n}{d})$. Therefore - we have $O(\frac{n}{d})$ parents in the array. For each parent we make $d$ comparisons, and finally we get the time complexity of $O(\frac{n}{d}*d) = O(n)$.


FFT implementation using Danielson-Lanczos Lemma I am trying to understand FFT algorithm explained here

FFT(x) {   n=length(x);
if (n==1) return x;
m = n/2;
X = (x_{2j})_{j=0}^{m-1};
Y = (x_{2j+1})_{j=0}^{m-1};
X = FFT(X);
Y = FFT(Y);
U = (X_{k mod m})_{k=0}^{n-1};
V = (g^{-k}Y_{k mod m})_{k=0}^{n-1};
return U+V;
}

The author says that the above comes from Danielson-Lanczos Lemma.

I am unable to understand what is the meaning of the lines:

X = (x_{2j})_{j=0}^{m-1};

Y = (x_{2j+1})_{j=0}^{m-1};

The meaning of the first line is "Let $X$ be an array of length $m$ (with indices running from $0$ to $m-1$) such that $X_j = x_{2j}$ for $j \in \{0,\ldots,m-1\}$." The second line has a similar meaning, with $Y_j = x_{2j+1}$ instead.


What is the difference between Multiprogramming and Multitasking I am finding it difficult to clearly differentiate between Multiprogramming and Multitasking.

My primary source has been Wikipedia, but the WP article seems to be a little at odds with some less reputable sources (like my college professor).

As I read WP, multiprogramming is a rudimentary way of increasing CPU throughput, by context-switching when a process waits for I/O.

  Multiprogramming doesn't give any guarantee that a program will run in a timely manner. Indeed, the very first program may very well run for hours without needing access to a peripheral.

Cooperative Time-sharing, synonymous with Cooperative Multitasking, is an improvement on multiprogramming (with which it is not synonymous). The CPU context-switches regularly to give the impression of simultaneous execution, but processes are still required to yield - and poorly designed programs can starve the rest of the system.

Preemptive Multitasking takes more aggressive control of scheduling, giving priority to some processes over others, etc.

Is this overview correct? If not is that because WP is incorrect or because I read WP wrong?
Why do some sources seem to conflate multiprogramming and multitasking?

They are more or less synonymous. Multiprogramming is more used when one CPU is involved, that is being switched from a process to the other, processes which are residing in memory simultaneously. Along came threads, and it wasn't switching between programs anymore...
Processors, particularly the intel line, had the mechanisms for true multitasking (timer interrupt, privileged instructions) since at least the 80286. The M68000 used in the very first Mac was a processor with full-fledged multitaking capacities. This isn't a recent development in architectures. Note that the very first time shared systems swapped the user's programs in and out, and thus weren't really multiprogramming in the sense of having several programs in memory at the same time.
The idea is to have several programs residing in memory simultaneously, so that when one yields the CPU (by finishing or by waiting) there are others ready to use the CPU, thus increasing CPU utilization (and as you can consider each CPU burst to be preparing for a use of I/O, increase overall usage). This gives better thoughput (important in batch systems).
Along came time sharing, several interactive users connected to the machine. Same idea, keep their programs around but switch among them fast enough so they have the ilusion of "having a computer to themselves". Requires a timer that interrupts the CPU to avoid monopolization.
On personal machines there was not much incentive to run several programs at a time, at least initially (one user in front of a severely limited machive didn't expect much). As machines grew, a way of working around this and allowing several programs at a time without changing the operating system much was "cooperative multitasking", in that every program is suposed to yield periodically to the operating system to select another one to run. As the program doing this is in full control, it can select to do this when nothing could get messed up by others. Needless to say, a program "forgetting" to fullfil its duty to yield gets an interesting boost in performance... early Mac systems worked this way, and for the above reasons this didn't last too long. On embedded systems with no or only rudimentary operating system, and a tightly controlled set of programs running, this is certainly an attactive option.


What's the difference between Adaptive Control and a Kalman Filter? From my basic understanding of Adaptive Control, I understand that it uses the error and the velocity of the error to approximate the error in the solution space of a problem, thus allowing for guaranteed convergence under certain conditions and rapid adaptation to changing conditions. I've accumulated this knowledge basically from anecdotal evidence and from this video.

From my basic understanding of a Kalman Filter, it takes into account the error from past measurements to estimate the current state with greater accuracy.

From my flawed perspective, they seem almost identical, but what's the difference between the two? I've heard anecdotally that they are duals of each other, but that the Kalman Filter is only for linear systems? Is this close to the truth?

The Kalman Filter only estimates the current state variables of the system, but doesn't (try to) influence the future state of the system. So a Kalman filter alone is just adaptive observation. I'm not sure whether it makes sense to say that adaptive observation is dual to adaptive control, because adaptive control implies some observation based feedback mechanism, while adaptive observation is just adaptive over time, but doesn't need any control based feedback mechanism, even so it doesn't exclude it.

A mathematically pure Kalman filter only applies to (discrete or continuous) linear system of the form $x_k = F_k x_{k-1} + B_k u_k + w_k$ where $F_k$ and $B_k$ are matrices, $u_k$ in the known control signal, $w_k$ is noise with a Gaussian distribution, and the observed signal is $z_k = H_k x_k + v_k$ with a matrix $H_k$ and noise $v_k$. However, the extended Kalman filter overcomes these restrictions sufficiently well, so that this is no real limitation. However, what stays true is that there should already be a sufficiently accurate model of the system. The noise terms allow to compensate for some model errors, but the overall model still has to be sufficiently predictive, because no adaptive model adjustment is performed, only the current state variables are estimated adaptively.

The video shows strongly nonlinear adaptive neural networks. This is completely different from Kalman filters, because here even the model of the system itself is adaptively adjusted. This resembles more closely what we do ourselves, in case our experiences don't match with out expectations and predictions.


Relationship between PP and PH Toda's theorem says that $PH \subset P^{PP}$.  Does this imply any relationship between $PH$ and $PP$ that does not involve oracles?  Does it imply either that $PH \subset PP$ or that $PP \subset PH$?  Is it known or conjectured whether either of those hold?

No, it's not known whether $PH \subset PP$, and it's not known whether $PP \subset PH$.  Neither of those is implied by Toda'a theorem.

This blog article cites a paper by Beigel giving some weak evidence to suspect that $PH \not\subset PP$ (that $PH$ is not contained in $PP$).  Please be warned that this is very weak evidence and doesn't really prove anything.  The result says that there's a relativized world where $P^{NP}$ is not contained in $PP$.  It follows that there's a relativized world where $PH$ is not contained in $PP$.  This might suggest the conjecture that $PH \not\subset PP$.  Or, at least, it suggests that proving $PH \subset PP$ might require special proof techniques (non-relativizing proof techniques; and most, but not all, known proof techniques do relativize).


What are the implications of P=NP? Is there a list of implications of $P=NP$?

Presumably, a proof of $P \ne NP$ will be by contradiction, for which a list of consequences of $P=NP$ would be useful.

If P=NP, then all of the NP problems can be solved deterministically in Polynomial time.

This is because the NP problems are all essentially the same problem, just stated in different terms.

As far as lists go -- many of the NP-Complete problems are enumerated here:
https://en.wikipedia.org/wiki/List_of_NP-complete_problems

Further implications? Our cryptosystems break down, armchair philosophers argue about what it means, the world changes, and somebody gets a Fields medal or Turing award + a big hunk of cash, etc... but that's a tangent.

For example, one of the classic NP problems is clique. If you could solve clique with a polynomial time algorithm, this would prove that P=NP, and then you could also use your method for solving clique to solve all of the other problems on that wiki-list, as an implication.


Is the following language context-free? $L= \{a^nb^m| m\geq2^n\}$ Is $L=\{a^nb^m|m\geq2^n\}$ a context-free language?

Let $p$ be the integer in Ogden's lemma, and consider the word $a^q b^{2^q} \in L$ for $q$ satisfying $2^q > p$, marking its $b$ part. According to the lemma, we can write $a^q b^{2^q} = uxyzv$ where $xz$ contains between one and $p$ letters $b$. Since $uyv \in L$ and $xz$ contains at least one $b$, it follows that it also contains at least one $a$. For $ux^2yz^2v$ to be in $L$, we need $xz$ to contain at least $2^{q+1}-2^q = 2^q$ letters $b$, contradicting our choice of $2^q > p$.

More generally, this works for any language of the form $\{a^nb^m : m \geq f(n)\}$ for any $f(n) = \omega(n)$, or even whenever $\limsup f(n)/n = \infty$.


What is the most efficient algorithm to get percentile distribution from histogram distribution? So let's say you have a histogram distribution represented as an array where each element is equal to the number of numbers from the underlying data set that are equal to that element's index.

For example, if your underlying data had 5 0's, 18 1's, 11 2's, 0 3's, etc., then the array representing this distribution would look like...
histogramBinSizes = [5, 18, 11, 0, ...]

Now, let's say you want to get the percentile distribution, which would be represented as an array where each element is equal to the number of numbers from the underlying data that fall in that percentile. What's the most efficient algorithm to get the percentile distribution array? (Maybe call this array percentileBinSizes)

To make the question easier, assume the numbers in the underlying data range from 0 to 100. That would make it so that histogramBinSizes and percentileBinSizes both have lengths of 101. Is there an even more efficient algorithm when this constraint is added?

I tagged this question with data structures as well as algorithms because I'm open to solutions that use a different data structure besides arrays. However, the input and output should still be arrays.

First, compute the cumulative distribution.  Suppose the input array is $A[0..n-1]$.  You can compute the cumulative distribution as follows:

Set $C[-1] := 0$.
For $i:=0,1,2,\dots,n-1$, do: set $C[i] := C[i-1] + A[i]$.

After this, $C[i]$ contains a count of the number of values in the underlying data set that are $\le i$.

Now you can compute percentiles directly from the cumulative distribution.  In particular, item $i$ is in the $\lfloor 100 C[i] / C[n-1] \rfloor$ percentile.  So, the output array can be computed as

Set $P[j] := 0$ for $j=:0,1,2,\dots,100$.
For $i:=0,1,\dots,n-1$, do:

Set $j := \lfloor 100 C[i] / C[n-1] \rfloor$, and set $P[j] := P[j] + A[i]$.

Now $P[j]$ contains the number of values from the underlying data set that fall into the $j$th percentile.  That was what you wanted to compute.

The running time is $O(n)$, where $n$ is the length of the input array.  It seems unlikely you can build anything that's any faster than that, as the problem seems to require reading the entire input.


Proving approximation ratio We recently in computational complexity class dealt with approximation algorithms and I was wondering how one would prove a heuristic having a certain ratio in regards to the optimal version. Looking at some notes it seems that one has to relate the approximation to an intermediate algorithm, right?

It's not necessary to compare to an intermediate algorithm, just to the best possible.

For example, consider the following terrible algorithm for approximating the distance between two vertices in a graph: if the vertices are adjacent, return $1$; otherwise, return $n$, the number of vertices.  This gives an $n/2$ approximation: in the worse case, the true distance is $2$ but the algorithm returns $n$.

But perhaps you're concerned that we might not know the true optimal value – after all, it's probably hard to analyze and compute. That's why we're using an approximation algorithm, right? So let's imagine that the distance between vertices is really difficult to calculate so we don't actually know what the worst case of our approximation algorithm is. At that point, you can start using approximations or, rather, bounds on the optimal value. So, for example, somebody might say, "Hey, I've no idea what the greatest possible distance between two vertices in a graph is but I know it's the length of the shortest path. A path has to use some set of edges, and use them once each. I know there can't be more than $n^2$ different edges in a graph, so the worst-case distance can't be more than $n^2\!$. Therefore, the approximation ratio can't be any worse than $n^2/2$." And they'd be right: the approximation ratio isn't any worse than that. The "more sophisticated" analysis in the previous paragraph gave a better bound on the approximation ratio.


2D packing in fixed dimensions rectangle Input:

a enclosing rectangle of size $(W, H)$
a family of rectangles $R= (R_1;R_2;\dots;R_n);R_i=(w_i;h_i)$

Output:

a scaling factor $s$
a 2D bin packing of $R$ in a rectangle of size $(sW, sH)$

I have a set of rectangles of various dimensions that I’d like to fit in an enclosing rectangle. This is a classic instance of the 2D-packing problem.
However, in my instance, the enclosing rectangle has fixed dimensions. All the rectangles should fit in it, but they possibly would have to be scaled and must keep their respective aspect ratios. They must not be rotated.

Most examples of 2D-packing algorithms find the enclosing square of least area, or assume that one of the dimensions isn't constrained.

I think that a good solution would be to find an enclosing rectangle R of aspect ratio (roughly) equal to that of the target fixed-dimensions enclosing rectangle T, then scale all the enclosed rectangles down with the ratio of R over T. It seems better to have a global ratio, so that rectangles keep their relative proportions.

I did not find any convincing algorithms, and cannot think of one except enumerating enclosing rectangles until one with a suitable aspect ratio is found.
Could you point me towards a working algorithm that I missed, or a better solution?

Related question, but the answer isn’t satisfying.

Imagine you want to display a bunch of pictures in a screen, however the screen's too small. So you display the picture in a virtual screen keeping the aspect ratio of the original screen, the scale the whole thing down.

Thank you!

This is equivalent to finding the enclosing square of minimum area for rectangles of size $(w_i/W, h_i/H)$.

You seem to have found algorithms for this problem already. There are many heuristics (here or here) and exact models (here), available when searching for "2D packing algorithm". The ones linked handle the case with variable W and H as well.


NP complete problems that are solvable in polynomial time if the input (e.g. number of variables) is fixed? I have seen some problems that are NP-hard but polynomially solvable in fixed dimension.

Examples, I think, are Knapsack that is polynomial time solvable if the number of items is fixed and Integer Linear Programming with fixed number of variables or constraints by Lenstras result.

Questions:

What are other examples of NP-hard problems that become polynomial time solvable if the dimension is fixed?

Are there problems for which this is not the case?

Is this always the case for problems that admit an FPTAS/pseudo-polynomial time algorithm such as Knapsack?

In parametrized complexity we solve the problem by fixing some parameter (say $k$).  If we are able to solve some problem in $f(k) \cdot p(n)$ time, we say the problem is fixed parameter tractable in $k$.  Here $f(k)$ is just some computable function.  There are lots of NP-hard problems that are FPT, however, there are many problems in NP that are believed to not be fixed parameter tractable.

If by fixing some parameter we can solve a problem in time $O(n^{f(k)})$, this problem is said to be in XP.  We believe that XP is not equal to FPT (just as we believe P $\neq$ NP).  But there are also lots of problems between these two (FPT and XP), and we have defined a hierarchy (actually several), one of those being the W-hierarchy.  In the W hierarchy you have reductions like reduction in NP-complete classes, except, we are not looking for polytime reductions, we just need an FPT reduction.  The class W[0] is the class FPT.

These are some samples in different classes of the W hierarchy:

Vertex cover is FPT (so is vertex disjoint paths on undirected graphs)
Independent set and Clique are both W[1]-complete
Dominating set is W[2]-Complete.

These are another level of complexities to classify NP problems in more precise way and if you want more you can look at this paper.

And if you want even more is good to read Grohe and Fomine's book

And finally:

  Is this always the case for problems that admit an
  FPTAS/pseudo-polynomial time algorithm such as Knapsack

Not necessarily, it's known that if the problem has FPTAS then it's also FPT (which is obvious), but there is some works on the relation of PTAS and XP, but there isn't very tight relation between PTAS and W hierarchy (at least I don't know at this moment).

Also in some cases may be we fix some different parameters, e.g: length of a longest path in the graph is bounded and size of a solution is bounded (e.g in feedback vertex set), ...


Existence of walk in undirected connected graph where nodes must end with assigned value We have a graph with $N$ nodes and $N-1$ undirected edges, where it's possible to reach one node from any other node. Each node will get assigned a value randomly from [1,...,10]. We want the value of every node to end up at 10. The way we update is as follows, whenever we visit a node, we increment the value of that node by 1 with wraparound (e.g. 7 -> 8 and 10 -> 1). We can revisit nodes and edges as we please. We don't initially advance the counter in our node we start from. Return the number of possible nodes we can start from, such that every node ends with value 10.

I tried just doing simple backtracking search on the states, but the complexity is way too high, and I don't know when I can say "not possible", since we can cycle from 10 to 1.

Let $k$ be the value where we wrap around, in this case $10$. Then the problem can be solved in $\mathcal{O}(n^2 k^2)$ with DP. With some tricks we will improve this to $\mathcal{O}(n k^2 \log n)$. For fixed $k$ this complexity is nearly linear, $\mathcal{O}(n \log n)$. Both algorithms work even on worst-case inputs: the assumption of random assignment of values is unnecessary.

We start from the $\mathcal{O}(n^2 k^2)$ algorithm. A connected graph with $n$ vertices and $n-1$ edges is a tree. To check if we can start from some vertex $r$, root the tree at that vertex. We will store the dp states $DP[i][t]$, which will denote if the subtree of vertex $i$ can be made to contain only the value $k$, if we cross the edge between $i$ and its parent $t$ times $(\text{mod}\ 2k)$, and our path starts from an ancestor of $i$. After calculating the $DP$, we know that the path may begin from $r$ iff $DP[r][2k-1] = 1$.

Note that we may assume that all edges are traversed at least once, since traversing any path back and forth $k$ times changes nothing. Additionally, crossing some edge $2k$ more or less times doesn't change whether a solution exists as long as we still cross it at least once, as we can re-connect the tours visiting these vertices such that we get a path that visits every vertex the same amount of times $(\text{mod}\ k)$.

Let $C_{i, j}$ denote the $j$th child of vertex $i$. Let $V_i$ denote the number of times we have to visit the vertex $(\text{mod}\ k)$ for its value to equal $k$. We have the requrrences

\begin{gather}
DP[i][2t_0] = \max_{\sum_{j} t_j = V_i\ (\text{mod}\ k)} \min_{j = 1, \dots, |C_i|}DP[C_{i, j}][2t_j]\\
DP[i][2t_0 - 1] = \max_{\sum_{j} t_j = V_i\ (\text{mod}\ k)} \max_{r = 0, \dots, |C_i|} \min_{j = 1, \dots, |C_i|}DP[C_{i, j}][2t_j + \mathbb{I}_{r}(j)]
\end{gather}
where $\mathbb{I}_{r}(j) = 1$ iff $r = j$.

The first recurrence holds, since if we cross the edge from $i$ to its parent $2t_0$ times and the edge from $i$ to its $j$th child $2t_j$ times, we visit $i$ exactly $\sum_j t_j$ times, which must equal $V_i\ (\text{mod}\ k)$. On the other hand, since the edges crossed an odd number of times form a path starting from $r$, and we cross the edge from $i$ to its parent an even number of times, we must likewise cross the edges from $i$ to its children an even number of times.

The second recurrence similarly holds, since if we cross the edge from $i$s parent to $i$ $2t_0 - 1$ times, $t_0$ of those crossings end in $i$, and if we cross the edge from $i$ to its $j$th child $2t_j + 1$ times, $t_j$ of those crossings end in $i$. Thus this sum must equal $V_i\ (\text{mod}\ k)$. The same path argument gives us that we may cross at most one edge from $i$ to its children an odd number of times.

These recurrences can be computed in $\mathcal{O}(|C_i| k^2)$ by initialising $DP[i][t] = \mathbb{I}_{0}(t)$, then looping over the children, at child $j$ assigning
\begin{gather}
DP[i][2t-1] \gets \max_{0 \leq t_1 < 2k} \max_{r = 0, 1} \min(DP[i][2t - 2t_1 - r],\ DP[C_{i, j}][2t_1 + (1 - r)])\\
DP[i][2t] \gets \max_{0 \leq t_1 < 2k} \min(DP[i][2t - 2t_1],\ DP[C_{i, j}][2t_1])\\
\end{gather}
At this point, $DP[i][2t-r]$, for $r \in {0, 1}$, is one if we can visit $i$ in total $t$ times, crossing the edge from $i$s parent to $i$ exactly $-r$ times $(\text{mod}\ 2k)$, but we need the amount of visits to equal $V_i$, so we finally assign
\begin{gather}
DP[i][2t] \gets DP[i][2V_i - 2t]\\
DP[i][2t-1] \gets DP[i][2V_i - 2t - 1]\\
\end{gather}

The complexity of checking one $r$ is thus $\mathcal{O}(\sum_i |C_i| k^2) = \mathcal{O}(n k^2)$, giving the complexity $\mathcal{O}(n^2 k^2)$.

We can optimise this by noticing that we calculate the same $DP$ values multiple times. However, the straightforward approach of leveraging this fails: calculating $DP'[i][p][t]$, where $p$ is the neighbour of $i$ that is an ancestor of $i$ might take $\mathcal{O}(n^2 k^2)$ time, even though there are only $4(n-1)k$ states: consider the star graph. To fix this issue, we use centroid decomposition.

The centroid is a vertex of the tree, such that if we root the tree at that vertex, every subtree will have size at most $\frac{n}{2}$. Such a vertex always exists. Our algorithm will work as follows:

Root the tree at the centroid $r$
Calculate $DP'[C_{r,j}][i][t]$ for all $j, t$ in $\mathcal{O}(nk^{2})$. This gives us the answer for $r$
Using these values, calculate $DP'[i][C_{r,j}][t]$ for all $j, t$ in $\mathcal{O}(|C_r| \log |C_r| k^2)$
Disable vertex $r$ and recurse to the remaining subtrees. Whenever we try to visit vertex $r$, just return the already calculated $DP$ values.

Before addressing how to do step 3, we'll calculate the complexity of this approach. At the $m$th (0-indexed) round, the size of every remaining subtree is at most $n2^{-m}$. Thus there are at most $\log n$ rounds. During the $m$th round, every remaining subtree is adjacent to at most $m \leq \log n$ already handled vertices. If $n_r$ is the size of the remaining subtree $r$ is in when $r$ is picked centroid, then steps 1-3 for that subtree take $\mathcal{O}((n_i + \log n) k^2 + |C_r| \log |C_r| k^2)$ time (due to the already handled at most $\log n$ vertices).

Since there are at most $\log n$ rounds, and the sum of $n_r$ of $r$ participating in that round is at most $n$, we have $\sum_{i} n_i \leq n \log n$. Thus the total complexity is

\begin{equation}
\mathcal{O}(\sum_{i} n_i k^2 + k^2 \log n + |C_i| \log |C_i| k^2) = \mathcal{O}(n k^2 \log n)
\end{equation}

since each term sums to at most this.

It remains to show how to do step 3. Note that our approach to calculating $DP[i][t]$ doesn't care about the processing order of the children. Say $|C_r| = 2^{m}$. First, using our approach, calculate the intermediate values for children with index in $[1, 2^{m-1}]$ and in $[2^{m-1} + 1, 2^{m}]$. At the $s$th (1-indexed) step, using the previously calculated values, calculate the values for children with index not in $[x 2^{m-s} + 1, (x+1) 2^{m-s}]$, for all $x$, in $\mathcal{O}(2^{m-s} k^2)$ time per interval (by including the other $2^{m-s}$ indices not in this inteval but in the interval in the previous step containing this interval). After the last step, we get $DP'[C_{r, j}][r]$ from the intermediate value for all children but $C_{r, j}$. This is indeed $\mathcal{O}(|C_r| \log |C_r| k^2)$.


Given a simple graph G, what's the quickest known way to sample one of its spanning trees at random? Let's say I have a simple graph G with an edge set E, vertex set V, and at least 1 cycle.

We can determine the number of spanning trees in this graph by finding its graph Laplacian matrix, striking out one row and column, and then taking the determinant of that sub-matrix.

Let's call that determinant t (i.e. there are t possible spanning trees in total).

What is the quickest known algorithm such that its input is G and it's output is one of t possible spanning trees of G (where each spanning tree has as close to $\frac{1}{t}$ chance of being selected as possible)?

Here's the algorithm I'm using currently.

Definitions:

$V_{visited}$ - vertices already traversed

$E_{visited}$ - edges already traversed

$V_C$ - V \ V_visited (i.e. vertices in V but not in $V_{visited}$)

N($V_{visited}$) - the set of all vertices v in $V_C$ such that an edge
exists between v and some vertex in $V_{visited}$

Algorithm:

sample $v_0$ from V randomly
add $v_0$ to $V_{visited}$
sample $v_1$ from N($V_{visited}$) randomly
add ($v_0$, $v_1$) to $E_{visited}$
sample $v_2$ from N($V_{visited}$) randomly
add ($v_*$, $v_2$) to $E_{visited}$ (where $v_*$ is a randomly chosen from $v_2$'s neighbors in $V_{visited}$)

...

sample $v_{|V| - 1}$ (the second to last vertex in V) randomly
add ($v_*$, $v_{|V| - 1}$) to $E_{visited}$ (where $v_*$ is a randomly chosen from $v_{|V| - 1}$'s neighbors in $V_{visited}$)
sample $v_{|V|}$ (the last vertex in V)
add (v*, $v_{|V|}$) to $E_{visited}$ (where $v_*$ is a randomly chosen from $v_{|V|}$'s neighbors in $V_{visited}$)

Now $V_{visited}$ and $E_{visited}$ represents a random spanning tree of G.

Is this the most efficient way of getting a random spanning tree? Is there a more efficient way? (Bonus points if it's parallelizable.)

I recommend Wilson's Algorithm. It is proven to select spanning trees uniformly at random. In worst case scenarios it can have complexity $n^3$, but in practical usage it often runs much faster, I believe typically $n log(n)$. I am part of a large research project at Duke and this is the algorithm we use. The current algorithm you have while faster, does not accurately sample randomly, one simple counter-example would be a star graph with an extra edge.

At the start, you have one visited vertex, and one exploring vertex (both randomly chosen). You start a random walk from the exploring vertex, until you hit a visited vertex. When the random walk makes a loop, you delete the loop from your walk, and carry on. When you hit a visited vertex, you append the vertices of your current walk to the visited vertices, and save the edges of the walk to the tree you will return. Then, you choose a new exploring vertex, and do another random walk, repeating until all vertices are visited vertices.

Here's a paper on Wilson's Algorithm and it's predecessor, the Aldous-Broder Algorithm. (which is worse in practice usually)


Families of sets indexed by another set I am reading Automata and Computability by Dexter C. Kozen and I am in the first chapter entitled Strings and Sets.
If we have a set $A=\{ab,b\}$ do we get to assume that the null string $\epsilon$ is also a member of that set? If we have another set $B=\{\epsilon\}$, does $A\cap B = \{\epsilon\}$ or does $A∩B=\emptyset$?
On a related note, I am having trouble understanding the meaning of a little chunk in the textbook. What does "family of set indexed by another set $I$" mean? What does the set $I$ consist of here? I am very confused by the notation as well. Anything you can do to help me understand the excerpt below is appreciated.

Set concatenation distributes over union:
\begin{align}
A(B\cup C) &= AB \cup AC, \\
(A \cup B)C &= AC \cup BC.
\end{align}
In fact, concatenation distributes over the union of any family of sets.
If $\{B_i \mid i \in I \}$ is any family of sets indexed by another set $I$, finite or infinite, then
\begin{align}
A \bigl( \bigcup_{i \in I} B_i \bigr) &= \bigcup_{i \in I} AB_i, \\ \bigl( \bigcup_{i \in I} B_i \bigr) A &= \bigcup_{i \in I} B_iA.
\end{align}
Here $\bigcup_{i \in I} B_i$  denotes the union of all the sets $B_i$ for $i \in I$. An element $x$ is in this union iff it is in one of the $B_i$.

The notation $\{ x_1,x_2,x_3,\ldots,x_n \}$ means "the set of elements $x_1,x_2,x_3,\ldots,x_n$". In particular, all elements in the set are listed. If an element isn't listed, it doesn't belong to the set. For example, $\epsilon$ is not an element of $\{ab,b\}$. There is absolutely nothing special about $\epsilon$. It is a bona fide word, and undergoes no special treatment. It is not an element of $\{ab,b\}$ just as $abba$ is not an element of $\{ab,b\}$.
As for your second question, here is a family of sets indexed by $I = \{a,b,c\}$:
$$ B_a = \{a,ba\}, B_b = \{b,ba\}, B_c = \{\epsilon,aa,bbb\}. $$
The union of this family is
$$ \bigcup_{i \in I} B_i = B_a \cup B_b \cup B_c = \{\epsilon, a, b, aa, ba, bbb \}. $$
The set $I$ is completely arbitrary. It could be the empty set, it could be a singleton, it could be a larger finite set, it could be an infinite set. For example, we can define a family of sets indexed by the natural numbers (including zero): for every $n \in \mathbb{N}$, $S_n = \{n,-n\}$. The union of this family consists of all integers: $\bigcup_{n \in S_n} S_n = \mathbb{Z}$,


Many to one reductions from undecidable Turing Machine to a decidable language From what I read, a many-to-one reduction $A \leq_m B$ means that $\forall x \in A$, there exists a computable function $f$ s.t. $f(x) \in B$. However, $f$ is not necessarily surjective (i.e. not all elements in $B$ have to be mapped).

But what if I try to reduce the language $ATM$ : {$(i,w)$ | $TM_i$ accepts $w$} to a well-known computable Turing-decidable language (i.e. $VERTEX-COVER$) using this function $f$:?

Where $f$: On input $(i,w)$, if Turing Machine $i$ accepts $w$, then a Turing Machine $M$ outputs a Graph $g$ that has a 2-vertex cover (any arbitrary graph with a valid 2-node vertex cover), and does otherwise.

In this case, $f$ is computable, and if $(i,w) \in A$, then $f(i,w)$ = $g \in VERTEX-COVER$. Since many-to-one reductions do not have to be surjective, I do not have to map all elements in the vertex-cover set, and yet, $g$ meets the conditions of the many-to-one reduction. There is also no necessary condition for $f$ to have a 'pullback' function $\hat{f}$, where $\hat{f}$ is an 'inverse' that maps all elements in vertex-cover back to $ATM$ since $A \leq_m B$ does $\textbf{not}$ necessarily imply $B \leq_m A$. (the pullback function $\hat{f}$ holds only if $f$ is surjective, which is not necessary in $\leq_m$).

Given the lemma, if $A \leq B$ and $B$ is decidable, then $A$ is decidable. In this case, $VERTEX-COVER$ is decidable, then $ATM$ should be decidable... which is clearly wrong.

There is something obvious that I am missing here ...

From what I read, a many-to-one reduction $A \leq_m B$ means that $\forall x \in A$, there exists a computable function $f$ s.t. $f(x) \in B$.

No. It's not "for each element $x\in A$ there exists a computable $f$ ...", but "there exists a computable total $f$ s.t. for each $x\in A$ we have $x \in A \iff f(x) \in B$".

Your definition is wrong because:

it allows us to pick a different function for each $x\in A$, when we must pick only one;
it only states $x\in A \implies f(x)\in B$, when we need the double implication $\iff$;
$f$ must be total (maybe this is supposed to be implicit when you don't say "partial", but it's important)

  However, $f$ is not necessarily surjective (i.e. not all elements in $B$ have to be mapped).

Correct.

  Where $f$: On input $(i,w)$, if Turing Machine $i$ accepts $w$, then a Turing Machine $M$ outputs a Graph $g$ that has a 2-vertex cover (any arbitrary graph with a valid 2-node vertex cover), and does otherwise.

How do you check that TM $i$ accepts $w$? I guess you are simply suggesting to simulate TM $i$. If you do that, there is a possibility of non termination here: precisely, every time $i$ diverges. Hence, $f$ is not total in this case: since its implementation diverges on some inputs.


Turing machine with semi infinite tape - Prove by construction I'm studying constrained Turing Machines.

There's a theorem that proves that both infinite and semi-infinite tape TM have the same computational power. The theorem that proves this by emulating a TM1 with infinite tape with a multi-track tape TM2, where one track emulates the right part of the TM1 tape and the other track emulates the left part TM1 tape.

Could I emulate the infinite tape machine the following way:

Let the alphabet of TM1 be {0,1}
Construct a TM2 machine with semifinite tape to right with alfabet {0,1} U {#}
Let w = 011101
When execution starts, the tape looks like
|011101BBB...
The first step of TM2 should be to call a subrutine TM2 that shifts w on the tape N times to the right and puts # in the first position of the tape, so: |#BB...011101BBB...
If during execution the control unit reads the # symbol, then call again the shifting subrutine.

I know this is not a formal prove, just an idea. I also know that this is not efficient nor an elegant construction but, could it work?

You are right. It is possible to shift the contents of the tape when needed.

The two track solution enlarges the alphabet $\Sigma$ to at least an alphabet $\Sigma\times \Sigma$ to store two symbols on each tape cell. That is quadratic. Your solution perhaps is more efficient in the number of symbols, since we merely have to move them into a new position.

A third proof might be to store the left and right cells of the tape (from an imaginary "middle") in the even and odd cells. That means the simulation would usually fins the next cell in two steps rather than one.

It is not always clear how to measure elegance of proofs :) sometimes a solution comes from a certain intuition, making it appealing.


Coprimes satisfying a pair We know that number of coprimes less than a number can be found using Euler's totient function.
But if there are two numbers $p$ and $q$ and we need to find number of numbers less than $q$ and coprime to $p$, is there any efficient method?

No.  This is as hard as factoring, and there is no known efficient algorithm for factoring.  In particular, there is a standard reduction to show that if you could compute Euler's totient function efficiently, then you could factor efficiently.


Show this function is partially computable Let B(x) be a computable predicate. Show that
\begin{equation}
G_B(r)=
\begin{cases}
1 \;\;\;\;\;\text{ if there are at least r numbers n such that B(k) = 1 }  \\
\uparrow \;\;\;\;\; \text{ otherwise}
\end{cases}
\end{equation}
I want to write a program with just these four instructions to compute $G_B$(r)

\begin{array} \\
\;\;\;\;\;\;\;\;\;Y \gets 0 \\
\;\;\;\;\;\;\;\;\;\text{IF } X \neq 0 \text{ GOTO } A \\
[E] \;\;\;\text{ GOTO } E \\
[A]\;\;\;\; Y \gets Y+1
\end{array}

The book gives examples for writing programs to compute $G(x_1,x_2)$ but does not give any when predicates are involved. Could someone give just an example for even a completely different function with predicates or just point me in the correct direction.

Since $B$ is a computable predicate, there is one procedure that computes it. We can call this procedure in any point of our program.

K <- k
i <- 0
LOOP
    RESULT <- B(i)
    IF RESULT != 0 GOTO TRUE
        GOTO ELSE
        TRUE
        K<-K-1
    ELSE
    IF K != 0 GOTO KEEP_GOING
        GOTO BREAK
    KEEP_GOING
    i <- i+1
GOTO LOOP

BREAK
RETURN 1

You will need to substitute the instruction K <- K-1 by an appropriate procedure.

To understand what is going on, we are looping through every natural number and checking whether it satisfies the predicate $B$, keeping a counter that diminishes every time we find one such number. So when the counter K reaches zero we know that the function should return 1, and we proceed to do exactly that.


sliding window maximum I have a stream of tuples arriving in the following form: (timestamp,price). There is no pattern in the arrival of these data points (number of data points per minute is random). I need to be able to return the maximum price in the last hour at any point of time. What is the most efficient algorithm in terms of time complexity and space complexity separately to do this ? I thought of the following:

create 1 min candles of prices, which will reduce the storage but then wont be exactly correct
store the top K elements with their price and timestamps and update this list according to the current timestamp

In the worst case, there is no algorithm with better space complexity than storing all data points from the past hour.  So, I think you should focus on optimizing time complexity.  A reasonable data structure would be to store them in a balanced binary tree, keyed on timestamp, where each node is augmented with the maximum price over all descendants of that node.  This achieves $O(n)$ space, if there are $n$ data points within the past hour, and $O(\log n)$ time per data point that you receive.


Are these three subset sum problems hard? How to solve them? After asking this question I was thinking about some variants of subset sum problem (SSP).

The usual subset problem is the following.

Instance: Given a set of $n$ integers and an integer $\sigma$.
Question: Is there a non-empty subset that sums to $\sigma$?

The three variants of subset sum that I thought about are (I assume that all integers are positive):

SSP1:

Instance: Given a set of $n$ integers $\{a_1,\ldots,a_n\}$, an integer $k\leqslant n$ and and integer $\sigma$.
Question: Is there a non-empty subset of cardinality at most $k$ that sums to $\sigma$? That is a subset $S$ for which $\sum_{i\in S}a_i=\sigma$ and $|S|\leqslant k$?

SSP2:

Instance: Given a set of $n$ integers $\{a_1,\ldots,a_n\}$, an integer $k\leqslant n$ and and integer $\sigma$.
Question: Is there a non-empty subset of cardinality at most $k$ that sums to at most $\sigma$? That is a subset $S$ for which $\sum_{i\in S}a_i\leqslant\sigma$ and $|S|\leqslant k$?

SSP3:

Instance: Given a set of $n$ integers $\{a_1,\ldots,a_n\}$, an integer $k\leqslant n$ and and integer $\sigma$.
Question: Is there a non-empty subset of cardinality at most $k$ that sums to at least $\sigma$? That is a subset $S$ for which $\sum_{i\in S}a_i\geqslant\sigma$ and and $|S|\leqslant k$?

My question is: Are these problems (SSP1, SSP2 and SSP3) hard?

My claim is the following: SSP1 is NP-complete but SSP2 and SSP3 are polynomial-time solvable.

My Proof (intuitive and incomplete):

For SSP1, if I can find a subset $S$ of cardinality at most $k$, then $S\neq\emptyset$ and hence I have solved SSP.
For SSP2, sort $\{a_1,\ldots,a_n\}$ in the ascending order. Select the first $k$ elements. If their sum is less than $\sigma$ then we are done. Else remove the biggest elements of the selected $k$ elements and see. Continue.
For SSP3, sort $\{a_1,\ldots,a_n\}$ in the descending order. Select the first $k$ elements. If their sum is greater than $\sigma$ then we are done. Else output no.

Is my work correct?

Your work is mostly correct:

SSP1 is clearly in NP. Moreover, it is NP-hard by reduction from SUBSET-SUM: given an instance of SUBSET-SUM, reduce it to the corresponding instance of SSP1 with $k = n$.
SSP2: Let $m$ be the number of negative elements in $\{a_1,\ldots,a_n\}$, and let $S$ be the sum of the $\min(m,k)$ smallest of them. Check whether $S \leq \sigma$. This is a polynomial time algorithm.
SSP3: Can be reduced to SSP2 by negating the set and $\sigma$. (We can also solve it directly just like SSP2.)


Counting number of perfect squares in an subarrays A sequence is good if the bitwise AND of all its elements is a perfect square.

So counting number of "good" sequences, in a subarray .

For example : in [1, 2, 3]

There are 6 sub-sequences:

So there are 3 "good" sequences

Can you suggest an efficient approach to count them ?

Take random 64 bit integers. What are the chances that the AND of the first ten has more than one bit set? So for random numbers, I’d say the count is close to n^2 / 2, and it takes cn operations for small n to count them all.

If $x=0$ or $x=4^k$ then x is a square, and x AND y is a square for any y. So if the AND of the first five numbers for example is one of these squares, then the AND of the first six, seven, eight, ..., n numbers is a square. Here's a simple algorithm:

total = 0
for 1 ≤ i ≤ n
    x = (all bits set)
    for i ≤ j ≤ n
        x = x AND a[j]
        if x = 0 or x = 4^k for some k
            total += n - j + 1
            break from for loop for j
        else if x is a square
            total += 1

This works well when the numbers are random. To improve for the worst case (for example alternating between 2 and 3, where this simple algorithm would take quadratic time), calculate the AND of groups of 2, 4, 8, 16, 32 etc. numbers, and observe that when calculating the AND of say a million 64 bit numbers, there will only be 64 different values. This is slightly complicated but not hard to implement if you are really interested in the solution.


Can the Hamiltonian path problem be solved by dynamic programming in $O(2^n n)$ time? Let G(V,E) be the graph and V = {$V_1$,$V_2$,....,$V_n$}. A dynamic programming approach solves the Hamiltonian path problem in $O(2^n n^3)$ time.

We can have a matrix :
dp[s][i][j] : which computes for any subset (say s) of V whether there exists a hamiltonian path starting from vertex $V_i$ and ends at vertex $V_j$ if s includes $V_i$ and $V_j$.

Can we have only dp[s][i] and say whether there exists a hamiltonian path ending at vertex $V_i$ there by solving it in $O(2^n n^2)$ time. Can it be improved furthur?

Yes, the problem can be solved in $O^*(1.657^n)$ time using algebraic methods. See the FOCS paper of Björklund [1].

[1] Björklund, Andreas. "Determinant sums for undirected Hamiltonicity." Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on. IEEE, 2010.


Logic formula for exactly n unique objects (no more, no less) I have a question in Logic:

If I am asked to construct a formula, using the '=' predicate, that shows that there are exactly n objects, I need to show that there are no n+1 objects, right?

For example, to show that there are exactly 3 objects, I will show that there are no 4 objects.

Also, I need to show that there exist n objects.

My question is, do I need to show that there is no case where only n-1 objects exist?

For example, to show that there are exactly 3 objects, do I need to show that there is no case in which there are only 2 objects?

If so, is that the correct form to do so? :

1) Showing that there is no case of 4 elements:

$
{\lnot}{\exists}x{\exists}y{\exists}z{\exists}w(x{\neq}y{\land}x{\neq}z{\land}x{\neq}w{\land}y{\neq}z{\land}y{\neq}w{\land}z{\neq}w)
$

2) Showing that there are 3 elements:

$
{\exists}x{\exists}y{\exists}z(x{\neq}y{\land}x{\neq}z{\land}y{\neq}z)
$

3) Showing that there is no case of only 2 elements:

$
{\lnot}{\exists}x{\exists}y{\lnot}{\exists}z(x{\neq}y{\land}x{\neq}z{\land}y{\neq}z)
$

And finally, combining the three:

$
(1){\land}(2){\land}(3)
$

I am really not sure.

Thanks in advance

EDIT:

Actually, assuming that I do need to show that there is no case of less than 3 elements (n elements), I would probably need to show that there is no case where there is just one element as well (from 1 until n-1), am I correct?

You need to say that (a) there are at least $n$ elements, and (b) there are at most $n$ elements.
To express (a),
$$
L_n := \exists x_1\dotsc \exists x_n\, \left( \bigwedge_{1\le i < j \le n} x_i\ne x_j \right).
$$
To express (b),
$$
M_n := \forall x_1\dotsc \forall x_{n+1}\, \left( \bigvee_{1\le i < j \le n+1}x_i = x_j\right).
$$
So the sentence $L_n \land M_n$ holds iff there are exactly $n$ elements.


Church-Turing Thesis and computational power of neural networks The Church-Turing thesis states that everything that can physically be computed, can be computed on a Turing Machine.
The paper
"Analog computation via neural networks" (Siegelmannn and Sontag, Theoretical Computer Science, 131:331–360, 1994; PDF) claims that a neural net of a certain form (the settings are presented in the paper) is more powerful. The authors say that, in exponential time, their model can recognize languages that are uncomputable in the Turing machine model.

Doesn't this contradict the Church-Turing thesis?

No, it's still consistent with the Church-Turing thesis, their model comes equipped with genuine real numbers (as in arbitrary elements of $\mathbb{R}$), which pretty much immediately extends the power beyond that of a Turing Machine. In fact, the title of 1.2.2 is "The meaning of (non computable) real weight", where they discuss why their model is built to include non-computable components.

There are in fact many models of computation that exceed the power of Turing Machines (q.v. Hypercomputation). The catch is that none of these are apparently able to be constructed in the real world (but maybe in the $\mathbb{R}$ world - sorry, couldn't resist).


Minimum number of rounds to notify a hierarchy of people with DP I'm trying to figure out a problem reported in Kleinberg (ch 6 no.16). I know that there are solutions based on ordering, anyway i'd like to understand if another way exists.

Basically, we have a hierarchy of people represented by a tree. The root person has to postpone a picnic due to rain: in a first moment he calls by phone his direct subordinates, one at a time. As soon as each subordinate gets the phone call, he must notify each of his direct subordinates, one at a time. This continues until everyone has been notified. Any person at a node can notify only his own children in the tree (e.g. no grandchildren).

You can view this process as being devided in rounds: in one round, every person who has been notified can call one of his subordinates (thus in parallel).

It's important to note that the number of rounds required to notify everyone depends on the sequence in which each person calls their direct subordinates. E.g. with the following tree we have 2 rounds if A notifies B first, or 3 rounds if A decides to start from D:

The problem requires an efficient algorithm that determines the minimun number of rounds. My approach is the following: like in largest independent set i obtain first a post order transversal $v_1, v_2, \ldots, v_n$ of the whole tree. Then i define the following recurrence relation:

$$
OPT(v_i)=
\begin{cases}
0 \qquad \qquad \qquad \qquad \qquad \qquad \quad \hbox{if leaf} \\
\displaystyle\max_{v_j\ \text{child of}\ v_i}\left\{k(v_i), 1 + OPT(v_j)\right\}  \ \hbox{otherwise}
\end{cases}
$$

Where $k(v_i)$ is the children count of the node $v_i$, and $OPT(v_i)$ is the minimum number of rounds required to notify the people contained in the subtree with $v_i$ as root.

Let's consider a more complex tree:

Due to the recurrence we have $OPT(v_i)_{v_i \in \left\{C, E, F, G, H, I, L \right\}} = 0$, $OPT(B)=4$, $OPT(D)=2$ and finally $OPT(A)=5$ that, as you can see, is exactly the minimum number of rounds to reach every node in the tree.

Please, if my approach is wrong can you give me some hint or counter example showing that ordering is required?

I do not think it is correct.Please consider this example:
Suppose $a$ has $k$ children. Two of them($b,c$) are chains of $k+1$ nodes the other are leaves.
We have:

$OPT(b) = OPT(c) = k$
All other $OPT$ are zeroes.

According to your algorithm we should have $OPT(a)=1+k$
But it is not correct:

let order of notifitions be $b,c,.....$

($c,b..$ is the same and the other are suboptimal)

Notification for the subroot of $b$ will stop at $0+(1+k)=1+k$ (time=0)
Notification for the subroot of $c$ will stop at $1 + (1+k)=2+k$ (time=1)
We don't really care about other leaves(they will all be notified by $k$)

This is different than the output to your algorithm.
The approach that FrankW proposed is the correct one!


How would the Internet work between planets? Say that in the future there are people on other planets, e.g., Mars.  The one-way communication delay to Mars is between 3 and 21 minutes.

Say we want to connect the people on Mars to the Internet.  How would we deal with the communication delay? For example, we don't want to get request timeouts as fast as we have them normally (on Earth).  Would network protocols need to be adjusted or modified to deal with the increased latency?

There would be special protocols for interplanet communication. Right now there are already different routing protocols for connecting different cities, different countries and different continents.

BGP (Border Gateway protocol) is a routing protocol used between continents mainly. It has different parameters and behavior than OSPF or RIP or other protocols used between different LAN's or WAN's.

Read about BGP. Some other protocols would probably be developed for even larger distances and for connecting different planets.


Finding the shortest path in a n-dimensional grid I have an $n$-dimensional grid space with two points on it defined by ordered pairs. I want to find the shortest path between the two points, but I can only increase one number in the ordered pair at a time. Is there an algorithm for this or at least one I can refer to?

It's easy: first get the 1st dimension right, then the 2nd dimension, then the 3rd dimension, etc.

For example, if you want to get from $(1,3,0)$ to $(3,4,1)$, you go via the following sequence of points: $(1,3,0), (2,3,0), (3,3,0), (3,4,0), (3,4,1)$.


Continuing the example of why it's hard to compute with univalence? In "Towards a cubical type theory without an interval" Altenkirch and Kaposi motivate why it is hard to compute with univalence. They say:

  For example, we can define the equivalence (not ,...) between Bool and Bool and thus univ (not ,...) : Bool =_U Bool, and then using it, define a boolean b:

coe : (A =_U B) → A → B
coe (refl A) a :≡ a

b : Bool
b :≡ coe (univ (not, ...)) true

  We know that b should be false as we coerce along not, but coe was only defined for the case refl so the term b does not compute further. One may think that it would be enought to add the equation coe (univ (f,...)) ≡ f but this is not sufficient as shown by the following example. Here we use the ap (apply path) function for a P : U → U :

ap_P : A =_U B → P A =_U P B
ap_P (refl A) ≡ refl (P A)

x : P Bool =_U P Bool
x :≡ ap_P (univ (not, ...))

  To reduce this term we need to know how to transport an equivalence along an arbitrary
  type.

What I don't understand is the last sentence. Is the "arbitrary type" the result of applying P to Bool? I feel that for any given P : U → U we can write a corresponding ap_P. For example:

Maybe : U → U
Maybe A = () + A

Show : U → U
Show A = A → String

Endo : U → U
Endo A = A → A

ap_Maybe (univ (f, g, ...)) = univ (either id f, either id g, ...)
ap_Show (univ (f, g, ...)) = univ (\show -> show . g, \show -> show . f, ...)
ap_Endo (univ (f, g, ...)) = univ (\endo -> f . endo . g, \endo -> g . endo . f, ...)

Is this intuition already off? What would be a concrete P where this fails? Or is the problem that while we know how to transport an equivalence along any function P : U → U we don't know how to do it for all such functions?

You are correct, in the sense that the elusive computational nature of Univalence is not so elusive for "ordinary" type constructors.

In fact, you might want to glance at Tabareau, Tanter and Sozeau's paper Equivalences for Free!, which outlines what you have just written, along with many more types of, well, types.

Trouble starts (as usual!) with dependent types, particularly when equivalent types start appearing in indices. Take the following type:

IndexedList (A : Type) : List A -> Type :=
   | INil : IndexedList A []
   | ICons : forall (a : A) (l : List A) (il : IndexedList A l), IndexedList A (a::l)

It's an interesting exercise to write down ap_IndexedList in this case, it's not trivial! But once this is done you then have to take into account types that depend on types that depend on $A$, etc. This is where things get pretty hairy.

Homotopy type theorists want to be able to describe this theory in full generality, since only this will capture the "ideal" of a constructive model of homotopy types.

But as Tabareau & al mention, this is not really all that useful for programing applications, where "single index nesting" is really all that is necessary (for the most part, obviously then proving things about dependent types might require more). So as far as computer scientists are concerned, we're pretty much ready for univalence!


Binary search with alternative comparison cost I have a sorted array $A$ of non-arbitrary elements. Now, I have another element $c$ and I want to find out where it belongs in the sorting of $A$. The cost of comparing $c$ to $A_i$ is $\Theta(i^2)$. I do not directly care about the number of comparisons, I just want to minimize the sum of the costs of the comparisons in the expected case (worst-case would also be nice).

Let's assume that each element in $A$ is unique and that $A$ does not contain $c$.

What is the optimal algorithm?

Let's say I told you in advance that $c$ is in the larger half. You still need $\Omega(\log n)$ comparisons, while now every helpful comparison takes $\Omega(n^2)$ cost, so the cost is always $\Omega(n^2\log n)$, which can be achieved with simple binary search.


Set partition refinement with subtrees In trying to design an algorithm, I needed a datastructure to implement a restricted kind of set partition refinement, where the sets $X$ to split on are subtrees. Specifically, given an arbitrary tree $T$ (computed earlier in the algorithm), and an initial partition where everything is in the same set, I need to do two things efficiently:

Refine the partition by splitting nodes in some subtree $T'$ of $T$ from the rest of the nodes.
Given a node $n$ in the tree, figure out the farthest (closest to the root) ancestor in its subset $S_n$.

The algorithm may have to do both up on (close to) every node on the tree, in any order. There's an obvious algorithm, similar to the one described on Wikipedia, where each node stores a pointer to the farthest ancestor in its set, and then when given a subtree $T'$ to split, we walk through every node in $T'$, and update the pointer to the root $r$ of $T'$ if it's an ancestor of $r$. The problem with this implementation is that since splitting can take up to $O(n)$ time (where $n$ is the size of the tree) to update all the pointers, the whole thing would be $O(n^2)$. Another implementation would be store, for each node, whether it's been split with its parent node. This makes splitting $O(1)$, since we just have to set the flag for the root node, but now finding the ancestor is $O(n)$ (we have to walk up the tree) so the whole thing is still $O(n^2)$. Is there a way to make this faster than $O(n^2)$ by taking advantage of the structure of the problem?

Yes.  You can build a data structure with the property that each operation takes at most $O(\log n)$ time.  Thus, your overall running time for doing $n$ operations will be $O(n \log n)$ instead of $O(n^2)$ -- a significant improvement.

As a warmup, imagine that the tree $T$ was balanced and in particular had depth $O(\log n)$.  Then it is immediate to see how to achieve $O(\log n)$ time per operation; your second approach suffices.  In particular, you set a flag in each node that is a split point.  Since the tree has height $O(\log n)$, walking up the tree takes $O(\log n)$ time.

What if $T$ isn't balanced?  We can generalize that answer.  Number the leaves of $T$ with the numbers $1,2,\dots,n$, from left to right.  Now build a new balanced binary tree $T^*$ with leaves $1,2,\dots,n$.  The shape of $T^*$ will be unrelated to the shape of $T$, but by construction the depth of $T^*$ will be $O(\log n)$.

Now, we store flags inside $T^*$ instead of inside $T$.  In particular, we will store a flag inside a node $v \in T^*$ if (1) the entire subtree of $v$ (including $v$ itself) is in the same partition, and (2) the parent of $v$ is in a different partition from $v$.  The flag identifies the partition that $v$ is in.  To find the partition that a node is in, you just walk up $T^*$, which takes $O(\log n)$ time.

And here is the key part.  When you split a partition, you can update the flags in $O(\log n)$ time.  In particular, when you split off a subtree of $T$, that corresponds to a set of leaves that are in a consecutive interval (namely, leaves numbered $i,i+1,i+2,\dots,j$ for some $i,j$).  But over in $T^*$, every consecutive interval is covered by a (disjoint) union of at most $O(\log n)$ subtrees of $T^*$.  So, you update the flags of the roots of those subtrees to reflect the new partition they are in.  That requires only $O(\log n)$ updates, so can be done in $O(\log n)$ time.


How can I draw a Moore diagram for a given circuit? I have a circuit and I should draw a moore diagram (state diagram) for that.  The problem is that every state can have 5 inputs and this makes the question hard for me.  I tried about 20 times to draw that diagram and every time I failed.  Can anyone help?

Don't try to draw the automata. Because there will be 32 states each having five transitions. Rather try to describe the transition function and output as hinted by DylanSp. i.e.

q01001 -> 1 -> q11001 (output 1), meaning if switches 2,5 are on and you put on switch 1, the lamp is lighted.

Another one.
q11001->2->q10001 (output 0), meaning if switch 1,2 and 5 are on and you put off switch 2 than the lamp is unlighted.

I assume that input consists of a sequence of 1,2,3,4,5 indicating which switch is flipped. starting state is q00000. I assume, final state will be probably those transitions where lamp is lighted, if that is what you are trying to do.


Balanced weight distribution in buckets, with different weight per bucket Is this problem a know variant of the optimisation version of the bin packing problem? There is an approximating algorithm for it?

Let $A = \{a_1,a_2,...a_n\}$ be a set of items, $B = \{b_1,b_2,...b_m\}$ be a set of buckets, with $m \leq n$. Each $a_i$ has a weight, based on the bin it is placed on (the item $a_i$ when placed on bin $b_j$ has weight $W_{i,j}$). Let $T(b_j)$ represent the total weight of the bucket $b_j$, $T(b_j) = \sum_{c=1}^t W_{c,j}$, which is the sum of the weights of each $a_c$ placed in $b_j$.
What is the optimal way to distribute all the items $a_i$ into the buckets $b_j$, such that each bucket $b_j$ has the almost same $T(b_j)$?

This problem came up when I'm trying to distribute a load in a distributed system, with distributed memory, such that each computer has almost the same amount of work. However, in my problem, when an item $a_i$ is placed in a specific computer, some other items from another set, say $x_{d..t}$, aggregate the work load on that server. The matrix $W_{c,j}$ is the map of the aggregated weights, for all choices of $b_j$ for the item $a_i$.

This problem is known as Unrelated Parallel Machine Scheduling. Minimizing $max_j T(b_j)$ has a 2-approximation, by LP-relaxation and rounding.