Questions tagged [algorithm-analysis]
Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage. Use the [runtime-analysis] tag for questions about the runtime of algorithms.
341
questions with no upvoted or accepted answers
9
votes
1
answer
1k
views
Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?
We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
- 261
8
votes
0
answers
2k
views
Choosing potential function in amortized analysis
How should I think to choose the potential function in the amortized analysis?
More specifically are there techniques or tips for choosing optimal or good potential functions?
- 81
7
votes
0
answers
539
views
What is the average-case running time of Fun-sort?
I read this paper: http://www.sciencedirect.com/science/article/pii/S0166218X04001131?np=y (you can check the PDF online for free), and I translated section 4's Fun-sort algorithm (correct me if I'm ...
- 71
7
votes
0
answers
360
views
Worst-case sparse graphs for Hopcroft-Karp Algorithm
Of large sparse biparite graphs (say degree 4) with N verticies, roughly speaking, which of them cause the worst case running time of the Hopcroft-Karp algorithm? What is their general structure and ...
- 699
7
votes
0
answers
191
views
What is the proof for the lemma "For every iteration of the Gomory-Hu algorithm, there is a representant pair for each edge"?
For a given undirected graph $G$, a Gomory-Hu tree is a graph which has the same nodes as $G$, but its edges represent the minimal cut between each pair of nodes in $G$. The Gomory-Hu algorithm finds ...
- 261
6
votes
0
answers
249
views
Is greedy minimax permutation rejecting sorting optimal?
I sketch an impractical, theoretical comparison sort.
Initialize a list of all $n!$ permutations of size $n$.
For each possible pair of indices $i, j$, count how many permutations would get rejected ...
- 12.5k
6
votes
0
answers
86
views
What are the properties of the unsided fold?
Foldl and folr are 2 very important functions for FP and Haskell, but I have never heard much about the unsided fold:
fold f [a,b,c,d] = (f (f a b) (f c d))
That ...
- 441
5
votes
0
answers
424
views
How to find the Expected height of a randomly built binary tree
I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $\frac{1}{2}$ probability of choosing right or ...
- 59
5
votes
0
answers
127
views
Count number of pairs $(a,b)$ in an array such that $(a + b)$ divides $(a * b)$
We are given an array of size $N$ with integer entries $> 0$. We have to count the number of all such pairs $(a,b)$ with $a \leq b$ such that $a*b$ is divisible by $a + b$.
The obvious naive way ...
- 203
5
votes
0
answers
60
views
Correctness of a zigzag algorithm to find the most similar vector in a bounded integer lattice
I am currently working on an integer lattice problem, called the "most similar vector problem," and wondering if can be solved correctly by a simple "zig-zagging" algorithm.
Given a real vector $u \...
- 429
5
votes
0
answers
1k
views
Alpha beta algorithm with Iterative Deepening analysis
I'm implementing a chess engine.
Like many engines, the search for the next best move is done with the alpha-beta algorithm. There are many improvements that can be made to make the algorithm faster ...
- 1,294
4
votes
0
answers
101
views
Distribution of pointer keys in a Skip-list node
Suppose we have a list of $N$ keys where the distribution of keys follows $f(x)$.
We construct a skip list over the keys.
Now if I pick a key (e.g. 31 in the ...
- 121
4
votes
0
answers
66
views
How advanced is the study of mathematically determining computational power comsumption?
I was thinking about how effective it would be to calculate the number of CPU instructions a section of code would have and then trying to estimate the energy cost for a program.
But I was curious if ...
- 203
4
votes
0
answers
70
views
Is there a known worst start configuration for Ford-Johnson sorting algorithm?
By this I mean a permutation of the $n$ input items to be sorted such that the number of comparisons taken to produce the correct order is maximal over all of the possible permutations of $n$ items.
...
4
votes
0
answers
789
views
What is the complexity of Hoffman and Pavley's Nth best path algorithm?
I am currently working on a project where I'm using an implementation of Hoffman and Pavley's "Method for the Solution of the Nth Best Path Problem" to find n-th best path through a directed graph. ...
4
votes
0
answers
2k
views
Show that the Minimum spanning tree Reduce Algorithm runs in O(E) on sparse graphs
This is a problem from CLRS 23-2 that I'm trying to solve. The problem assumes that given graph G is very sparse connected. It wants to improve further over Prim's algorithm $O(E + V \lg V)$. The idea ...
- 309
3
votes
0
answers
77
views
Running time analysis of Savitch's algorithm
Savitch provided an algorithm which places NL in L^2 and hence the runtime of the algorithm is bound by $2^{O(\log^2n)}$. The runtime of the algorithm is not in P as NL is not known to be in SC.
Is ...
3
votes
0
answers
44
views
Hardness of an instance of a problem independent of algorithms?
The paper “Where the really hard problems are” (https://www.ijcai.org/Proceedings/91-1/Papers/052.pdf) and others that cite it provide evidence that lots of algorithms for many NP complete problems (...
- 217
3
votes
0
answers
34
views
Suggestions for a source of algorithm design problems?
I’m finishing up Roughgarden’s two-part algorithms course on edx, and it was good, but I didn’t actually ‘design and analyze’ many algorithms, the questions mostly tested whether you understood the ...
- 153
3
votes
1
answer
99
views
Max sum cyclic path of fixed length in matrix
Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves ...
- 31
3
votes
0
answers
389
views
Tail recursion can't work with dynamic programming programs
I am doing some exercises on dynamic programming in order to get familar with this concept.
I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic ...
- 31
3
votes
0
answers
114
views
Formal justification of the accounting method and its meaning
I'm reading through CLRS again and I was wondering if there's a formal justification or construction of the accounting method, explaining why it works. For some reason it seems to me that CLRS ...
- 683
3
votes
0
answers
680
views
Greedy max k-cut approximation algorithm
I'm trying to formulate a greedy algorithm for the Max k-cut problem:
Let's have an not oriented graph $G(V,E)$, each edge $e \in E$ has its weight $w_e$. The goal of the algorithm is to divide all ...
- 151
3
votes
0
answers
46
views
Is it possible, at least in theory, to "lockfree-ize" algorithms algorithmically?
The problem emerged from a practical case, but thinking on it resulted more and more theoretical directions.
Typically, the lock-free algorithms do relative simple things in the practice, but their ...
- 416
3
votes
0
answers
57
views
Examples of algorithms with low spacetime complexity
When running a data center, one of the cost metrics you might care about is "ram seconds". For example, an algorithm that holds 1 MB of memory for five minutes consumes 300 million ram seconds. A ...
- 5,772
3
votes
0
answers
119
views
Will quantum computers out-scale classical computers at P-problems?
It is my understanding that quantum computers have gained interest, because some interesting problems are suspected to be in the BQP-class, but not in the P-class (integer factorization, ...). Quantum ...
- 31
3
votes
0
answers
2k
views
What is the Big-Oh asymptotic complexity of learning in Random Forests?
Random Forests is a bagged ensemble of CART learners. The following is what I've found, but am not sure if I'm completely right.
CART (Classification and Regression Trees) uses the Gini index for ...
- 143
3
votes
0
answers
1k
views
Analysis of Weighted Quick Union with Path Compression
I have searched the internet for an analysis of why WQUPC is amortized $O( m \alpha (n) ) $ for m operations on n nodes ( $\alpha ( n) $ is the inverse Ackerman function).
I understand why it is $O ( ...
- 31
3
votes
0
answers
47
views
Running time for threshold function evaluation?
A threshold function is a function $f: \{0,1\}^n \to \{0,1\}$, defined by $n$ integer-valued weights $w_1, w_2, \ldots, w_n$ and an integer valued threshold value $w_0$. It works as follows:
$$f(x_1, ...
- 31
3
votes
0
answers
279
views
Approximation ratio of a greedy grid-cover algorithm
We're given a $N\times M$ grid, and we want to cover all coordinates in the greedy by rectangles of size $\le k$.
Consider the following greedy algorithm. At each iteration, it chooses a rectangle ...
- 2,624
3
votes
0
answers
1k
views
Why is my bubble sort taking longer to sort a random array as opposed to a descending array?
I am in an entry-level algorithms class, and for our final project we are coding and thoroughly analyzing 6 different sorting methods. Part of the analyzation is timing the methods and comparing the ...
3
votes
0
answers
256
views
Gradient descent vs. Newton's method: which is more efficient?
Using gradient descent in d dimensions to find a local minimum requires computing gradients, which is computationally much faster than Newton's method, because Newton's method requires computing both ...
- 1,217
3
votes
1
answer
162
views
Why does a prepare message wants a promise that an acceptor is never to accept a proposal numbered less than its propose sequence value? (Paxos)
I was studying Paxos from:
http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf
Recall that Paxos is a distributed system algorithm with the goal that the processes ...
- 2,950
3
votes
0
answers
1k
views
Node potentials of minimum cost flow successive shortest path algorithm
I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
- 231
3
votes
0
answers
444
views
Expected depth of modified kind of treap
If we have $n$ elements $s_1, \dots, s_n$ and build a kind of treap (tree-heap) out of it. Each $s_k$ has a priority, which is an integer in $\{ 1, 2, 3 \dots, \lceil \log n \rceil\}$. Since the ...
3
votes
0
answers
799
views
Analysis of a linear-time algorithm for longest palindromic substring
Background
$\newcommand\ldotd{\mathinner{..}}$Last month, I heard about a new linear-time algorithm to determine the longest palindromic substring called Jeuring's algorithm. It seemed interesting, ...
- 621
3
votes
2
answers
8k
views
Best case analysis for Shell sort
The exercises in a textbook I studied asks about the best case for Shell sort. I have scribbled a derivation for the same along the margins almost two years ago. Basically I don't know if this was my ...
- 529
2
votes
0
answers
47
views
2
votes
0
answers
171
views
How to Show Subset Sum $\le_p$ 3-Partition
Given a set of integers S (positive and negative, may contain duplicates) can S be divided into three disjoint subsets that all sum to the same value? Prove this problem is NP-complete.
Is it ...
- 21
2
votes
0
answers
184
views
CLRS Exercise 6.4-5
The question is as follows:
Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg n)$
https://walkccc.github.io/CLRS/Chap06/6.4/
This website provides a ...
2
votes
0
answers
193
views
How does the maximum number of guesses needed to win Mastermind (board game) change as the size of the board increases?
Donald Knuth demonstrated that the codebreaker in the board game Mastermind can solve the pattern in five moves or fewer using the following algorithm:
Create a set S of remaining possibilities (...
- 33
2
votes
0
answers
555
views
Understanding the behaviour of different variations of Binary Search
Binary Search is a fairly simple and standard algorithm that can be used (among other things) to find a target element in a sorted array. There are subtle variations in code to do this, however all of ...
- 121
2
votes
0
answers
40
views
When does knowing the number of solutions help (improve the running time)?
Combinatorics equips one with methods to find the number of solutions to discrete problems. While this is obviously an important tool for accurate gauges on the average running of an algorithm, I'm ...
- 659
2
votes
0
answers
50
views
Theoretical performance measures other than worst case
Suppose that $P \neq NP$, and $P = BPP$.
Assume one is given a decision language $L \in NPC$, and she has only polynomial time turing machines. Additionally, she can't use randomness (not sure that's ...
- 81
2
votes
0
answers
507
views
Analysis expected depth of a binary search tree given random values?
I have a guess about the problem above. Suppose I have a binary search tree $T$ initially empty. Suppose I drawn $x_1,\ldots,x_k$ (from some real interval $[a,b]$) keys and I want to insert the keys ...
- 683
2
votes
0
answers
111
views
Sorting Algorithm: Probability Bound For Randomized Inversion Swapping
Let $A = (a_1, a_2, \dots, a_n)$ denote an array of distinct values with an order defined. Consider the following randomized sorting algorithm.
Let $m := 0$.
Select a pair $(i, j)$ with $1 \le i < ...
- 389
2
votes
1
answer
469
views
A* 8-puzzle problem worst case memory usage
We are testing the A* algorithm with Hamming and Manhattan on the 8-puzzle (and its natural generalization n-puzzle) problem.
We have to answer the following question but I can't figure out what it ...
- 21
2
votes
0
answers
290
views
Sedgewick analysis of algorithm, difference between theory of algorithm and scientific approach
I'm trying to improve my skills in analysis of algorithms. I think Sedgewick's "introduction to the analysis of algorithm" is a good, I'm reading carefully the first chapter, at least I'm trying. And ...
- 683
2
votes
0
answers
30
views
Comparison of Swarm Intelligence Algorithms with Constraint Violations
I want to compare swarm intelligence algorithms in a optimisation problem. As far as I understand, a typical approach is to perform several runs of each algorithm (say 30 independent runs, with ...
- 21
2
votes
0
answers
1k
views
Help with deterministic selection algorithm
All we know what is Deterministic Selection Algorithm:
Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group ...
