Sam Westrick
  • Member for 4 years, 11 months
  • Last seen more than a month ago
Find the shortest path that goes through an even number of red edges
Accepted answer
7 votes

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 ...

View answer
Plain-language example of how a functional style makes parallel programming easier
Accepted answer
3 votes

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 ...

View answer
Insert a node in a binary search tree
Accepted answer
3 votes

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 ...

View answer
What would be the big O notation for a function that attempts to find pairs of users that participate in different discussions?
2 votes

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 ...

View answer
MST with degree constraints on some node
2 votes

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 ...

View answer
rebalance red-black tree with many violations
Accepted answer
2 votes

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. ...

View answer
What do we benefit from using ternary search trees rather than binary search trees?
2 votes

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 ...

View answer
The longest path in a tree
Accepted answer
2 votes

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 ...

View answer
GroupBy key a sequence of ordered key values
Accepted answer
1 votes

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 ...

View answer
Parallized algorithm for getting the frequencies of numbers in an array
1 votes

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 ...

View answer
Formal definition of the Dynamic Array - what is the Dynamic Array
1 votes

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 ...

View answer
Do dynamic/static languages associate types or classes to values or variables?
1 votes

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....

View answer
Calculate Shortest Path (Shortest Time) Through a Store in a Graph
Accepted answer
1 votes

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 ...

View answer
how does the parallel radix sort work?
1 votes

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 ...

View answer
Rotations in a treap
Accepted answer
1 votes

Initially, node F is violating the heap invariant. Its priority is too small, and it needs to be moved up the treap. The only operation needed is a single rotation. If you are not already familiar, ...

View answer
Forming red-black tree from binary tree conserving in-order traversal
Accepted answer
1 votes

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 ...

View answer