New answers tagged

-1 votes

Examples of algorithms best their class that require cyclical data structures

Any graph algorithm that works on general graphs (i.e., is not restricted to acyclic graphs) qualifies. You should be able to look through your favorite textbook and find many algorithms that work on ...
D.W.'s user avatar
  • 158k
1 vote
Accepted

Data structure to keep track of cache hit ratio?

What you're looking for is not so much a data structure as a problem statement. What is it that you're trying to learn from a metric such as a hit-count? The structures need to match what you're ...
Cort Ammon's user avatar
  • 3,286
1 vote

How to optimize algorithm to solve the following time series problem?

First, apply the standard reduction: to solve a ratio maximization problem (sometimes called "fractional programming"), binary search on the solution $t$: $$ \max_x \frac{f(x)}{g(x)} \geq t \...
pcpthm's user avatar
  • 2,339
6 votes
Accepted

Improving a ranking system with "best rank"

Each query can be implemented to run in $O(\log n)$ time by lazily propagating appropriate operators on the binary search tree. The lazy propagation technique *1, is that it is possible to perform ...
pcpthm's user avatar
  • 2,339
0 votes

prove that in binary heap buildheap function does at most 2N-2 comparison

we're focusing on the final step of the process. At this point, we assume that the two child heaps are already built and properly organized. The cost to "fix" the heap at this stage is given ...
fvifvifvi's user avatar
0 votes

Recursive formula for height of BST

In addition to the upper bound in https://cs.stackexchange.com/a/96451/12322 Lower bound $\displaystyle E(Y_n)= \frac{2}{n} \sum^n_{i=0}(E[2\max(Y_{i−1},Y_{n−i})] + 1) \geq \frac{2}{n} \sum^{n-1}_{i=...
Subhankar Ghosal's user avatar
2 votes

Recursive formula for height of BST

The formula is wrong. Indeed, we can find by hand that $H(1) = 0$, $H(2) = 1$ and $H(3) = \frac95$ ($5$ different trees, $4$ of them being of height $2$, the last of height $1$). But: $$\frac13\sum\...
Nathaniel's user avatar
  • 13.9k

Top 50 recent answers are included