Sam Westrick
• Member for 4 years, 11 months
• Last seen more than a month ago

Here's a nice way to do it. Make two copies of the input graph; call them $A$ and $B$. Now redirect the red edges so that they jump across to the other copy, but leave the blue edges untouched. Any ...

Functional programming is great for parallel programming that is not concurrent. The example problem you gave is inherently concurrent, but we can make it non-concurrent by "batching" the ...

It seems like this algorithm is keeping track of parent pointers. Each node N has three fields: N.left (left child), N.right (right child), and N.p (parent). The variable y is used to keep track of ...

It might be nice to model the problem as a bipartite graph $(U, C, E)$ where $U$ is the set of users, $C$ is the set of conversations, and $E \subseteq U \times C$ are edges for participation. In this ...

Here's an algorithm that just reduces to MST; no need to modify Prim's or some other algorithm. The idea is simple: remove $v$, compute the MSTs of the resulting components of the graph, and then ...

In general, I would say that the algorithm you want is a tree union (also called a merge), which takes two trees and combines them so that the new tree contains the union of the keys of both inputs. ...

I'd challenge you to write the code which queries your data structure. For example, how could you determine that "SARAS" is in your tree, but "KSARAS" is not? The problem with your data structure is ...

I'm guessing that $d(v)$ is the degree of $v$, in which case this is fairly straightforward to prove. Here's some intuition: the longest path cannot end with a vertex of degree 2 or more, because then ...

Since the input is sorted, the elements are essentially already grouped, you just need to find the "boundaries" between the groups. By boundary, I mean the index where a run of the same key ...

One option would be to sort the data and then compute offsets where runs of equal integers appear in the sorted array. Then, the frequencies are just differences in these offsets. Computing the ...

I'm not sure what you mean by this: I have never seen, in any programming language ever, any specialized Data Structure called Dynamic Array, nor can I find any ADT which is implemented by Dynamic ...

In those bullets, Harper is addressing common misconceptions about static versus dynamic typing. Each of those bullet points starts with a misconception, and then continues with Harper's clarification....

You can do this with two instances of shortest paths. You need to know the shortest distance $d(A,S)$ for each store $S$. This is just Dijkstra from source $A$. You also need to know all the shortest ...

It turns out that within each round of radix sort, we can take advantage of parallelism. We need to reorder the keys (in a stable manner) according to the relevant bit. The simplest to do this in ...

Iterative insertion gives a time complexity of $O(n \log n)$ for $n$ keys, but it's possible to do it in linear time. The input tree gives you the in-order traversal, so you can begin by traversing ...