# Questions tagged [ds.algorithms]

Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.

1,608 questions
Filter by
Sorted by
Tagged with
564 views

### Minimum spanning tree algorithm. [closed]

Is the following a valid algorithm for finding a minimum spanning tree? Given a weighted graph with unique weights, remove the all edges that are the highest cost edge in any cycle of the original ...
10k views

### How hard is unshuffling a string?

A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a ...
388 views

### Best resources for string searching or pattern matching exercises

I would like to be somewhat good at string searching and pattern matching, could you point me to some good online resources? Exercise problems would be great. Thanks.
790 views

### Online transitive closure better than O(N^2) per edge addition

I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this: ...
3k views

### Complexity of the Fisher-Yates Shuffle Algorithm

This question is in regard to the Fisher-Yates algorithm for returning a random shuffle of a given array. The Wikipedia page says that its complexity is O(n), but I think that it is O(n log n). In ...
291 views

### Generalizing the FFT

Can the divide and conquer nature of the FFT be generalized to other transforms (z Transform, chirp, etc) automatically? Is there an algorithm that takes in a description of transform (I don't know ...