Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage.
2
votes
0answers
14 views
How approximate are “approximate” nearest neighbor (ANN) search algorithms?
Starting to use nanoflann to do some point cloud nearest neighbor searching and it got me thinking about just how "approximate" ANN methods are.
If I have a (more or less) randomly distributed point ...
2
votes
1answer
59 views
Complexity of an algorithm for bounding a region in 2D
First I apologize if the title is unclear, but I didn't find anything better.
I want to find the boundary of (a simply connected) region in the $x-y$ plane. I'm solving a differential equation with ...
2
votes
2answers
54 views
Are those definitions of universal hash family equivalent?
I've seen two definitions of a universal hash family, and my questions is if those are equivalent, i think they are and will explain why but i'm not sure if it is.
Definition 1:
$H$ is a universal ...
2
votes
0answers
29 views
Why does Shellsort work well on Sorted and Reverse ordered lists?
I've ran some tests and found that Shellsort runs much faster on ordered and reversed lists compared to random lists and almost ordered lists.
...
1
vote
1answer
46 views
Find longest common subsequence in limited space
Given three strings $x$, $y$, and $z$ over an arbitrary finite alphabet, I need to determine their longest common subsequence (LCS).
Example: A longest common subsequence of ...
3
votes
1answer
39 views
Is this simplified consensus problem easier than the original?
There is a famous Consensus Problem in Distributed Computing.
Let's consider and try to find the best possible algorithm for a simplified version of the consensus problem.
Assumptions: a process ...
5
votes
2answers
96 views
Understanding why the polynomial $p(n) = \sum_{i=0}^{k} a_in^i$ is in $\Theta(n^k)$
Hi I've read this lemma in my book:
Lemma 2.1. Let $p(n) = \sum_{i=0}^{k} a_in^i$ denote any polynomial and assume $a_k > 0$. Then $p(n) \in \Theta(n^k)$
Proof. It suffices to show that ...
1
vote
0answers
33 views
Solving a variant of interval scheduling problem
I am trying to solve a problem of finding compatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.
I have a ...
0
votes
1answer
38 views
Confusion related to calculating time complexity
I have some confusion related to calculating the time complexity of this algorithm
opt(i)
for j=i:n
a = f(i,j) + opt(j+1)
end
How is the running ...
4
votes
1answer
66 views
Find the longest subsequence of two strings
I want to know which is the best way to find the longest common subsequence of two strings
-3
votes
0answers
39 views
Finding a better algorithm for a problem [closed]
Interval scheduling.
Job j starts at sj and finishes at fj
What is the best way to solve this?
2
votes
1answer
62 views
Euclidean Steiner Tree Question in Approximation Algorithms
Given $n$ points in $\mathbf{R}^2$, define the optimal Euclidean Steiner tree to be a minimum (Euclidean) length tree containing all $n$ points and any other subset of points from $\mathbf{R}^2$.
...
2
votes
1answer
40 views
Solving a problem related to convolution
I have this confusion related to solving this problem
You’vebeenworkingwithsomephysicistswhoneedtostudy,aspartof their experimental design, the interactions among large numbers of very small charged ...
1
vote
1answer
39 views
Finding the lower bounds of an algorithm
I am struggling to calculate the lower bounds of an algorithm. What is the right way to proceed.
For eg, I have the following algorithm
...
-1
votes
1answer
23 views
Algorithmic analysis using log [duplicate]
How would I solve the following.
An algorithm that is O(Lg_2 n) takes 10 seconds to execute on a particular computer when n=100, how long would you expect to take it when n=500?
An algorithm that ...
0
votes
0answers
48 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 ...
2
votes
1answer
40 views
Fractional Knapsack in linear time
How to solve fractional knapsack in linear time? I found this on Google but don't really understand it.
Choose element $r$ at random from $R$ (set of profit/weight ratios)
Determine
$R_1 = \{ p_i ...
1
vote
1answer
53 views
Backtracking for listing k elements
Can someone give me a hand here, I am new to backtracking, and preparing for an interview. I couldn't even attempt this question, please help.
Describe a back tracking algorithm for efficiently ...
1
vote
0answers
45 views
LInear time algorithm to find the diameter of a tree [duplicate]
This is NOT HW, this is from Skienas book, and I just couldn't solve it at all.
Please give me a hand here, in understanding and solving it, thanks.
Let G = (V, E) be a binary tree. The distance ...
0
votes
1answer
69 views
Why does DFS only yield tree and back edges on undirected, connected graphs?
Prove that if G is an undirected connected graph, then each of its edges is either in the depth-first search tree or is a back edge.
Now, from intuition and in class lectures by Steven Skiena, I know ...
2
votes
1answer
25 views
Can you convert a positively weighted DAG into a non-weighted DAG in polynomial time?
Given a positively weighted DAG (directed acyclic graph) $D = (V,E)$, can you create a new non-weighted DAG $D'$ by converting each edge with weight $w(e) = x$ into x non-weighted edges and vertices? ...
14
votes
2answers
227 views
What's harder: Shuffling a sorted deck or sorting a shuffled one?
You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a < b$) and a truly random source of bits ...
3
votes
2answers
68 views
Finding no. of leaf nodes for each node in a BST
A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is
$\qquad ...
4
votes
1answer
43 views
Parallel merge sort using hypercube connection template
I've been reading about hypercube connection template for parallel algorithms. The general scheme is explained in Designing and Building Parallel Programs by Ian Foster and it's pretty clear.
What I ...
0
votes
1answer
42 views
Proving correctness of the algorithm for convex polygon minimum cost triangulation
I have read many solutions for the minimum cost of triangulation problem and intuitively get the idea , however I am struggling to figure out how to prove it formally. I kind of feel that it has to be ...
2
votes
0answers
22 views
Differences between Fuzzy C-Means and EM
When clustering a set of data points, what exactly are the differences between Fuzzy C-Means (aka Soft K-Means) and Expectation Maximization?
In slide 30 and 32 of this lecture I found, it says that ...
4
votes
1answer
46 views
Prize collecting steiner tree
I'm reading about the prize collecting steiner tree problem and an approximation algorithm that uses randomization to set a lower bound on the optimal solution (see Chapter 5.7 in The Design of ...
0
votes
0answers
56 views
Complexities of basic operations of searching and sorting algorithms
Wiki has a good cheat sheet, but however it does not involve no. of comparisons or swaps. (though no. of swaps is usually decides its complexity). So I created the following. Is the following info is ...
1
vote
1answer
45 views
While proving optimality of the A* algorithm, why can we change graphs?
In the original paper of A* algorithm, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, the author proved the optimality of A* in Theorem 2, page 105.
However, I cannot ...
1
vote
2answers
175 views
Why is $\Theta$ notation suitable to insertion sort to describe its worst case running time?
The worst case running time of insertion sort is $\Theta(n^2)$, we don’t write it as $O(n^2)$.
$O$-notation is used to give upper bound on function. If we use it to bound a worst case running time of ...
0
votes
0answers
53 views
Question about amortized analysis
Consider a dynamic table, where it expands when you fill a certain amount, and contracts when there is small enough elements.
Let $e$ be an arbitrary function which is the constraint to expand.
Let ...
1
vote
1answer
55 views
How to get expected running time of hash table?
If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in ...
1
vote
3answers
69 views
Loop Invariants as Tautologies
Would it be correct to characterize loop invariants as a type of tautology? I ask since the invariant must basically always be true, before the loop starts, before each iteration and after the loop ...
1
vote
0answers
21 views
Potential function in amortized analysis [duplicate]
I am trying to calculate the amortized cost of a dynamic array, that's size becomes 4 times the size when the array is filled. (when you re-size, you create a new one and copy the elements there).
...
3
votes
1answer
105 views
How to compute amoritized cost for a dynamic array?
I am trying to understand how to do the amortized cost for a dynamic table. Suppose we are using the accounting method.
Let A of size m be an array of n elements. When $n = m$, then we create a new ...
-2
votes
1answer
89 views
Complexity of slightly tricky for loop
I'm trying to determine the complexity of this for loop:
for (int j =3; j <= n-2; j+=2) {
....
}
By trying out lots of examples, I came up with ...
-3
votes
1answer
91 views
Complexity of a while loop that divides by parameter by three each iteration
I've learned that a while loop such as
int i = 100;
while (i >= 1){
...
///Stuff
i = i/2
}
will run in logarithmic time, specifically, ...
1
vote
2answers
70 views
Common Algorithms without Asymptotically Tight Bounds
I can think of functions such as $n^2 \sin^2 n$ that don't have asymptotically tight bounds, but are there actually common algorithms in computer science that don't have asymptotically tight bounds ...
2
votes
2answers
59 views
Need help about solving a recurrence relation
I have a recurrence relation which is like the following:
$T(n) = 2T(\frac{n}{2}) + \log_{2}n$
I am using recursion tree method to solve this. And at the end, i came up with the following equation:
...
4
votes
1answer
74 views
How to get the expected running time of an algorithm
I have an algorithm which, basically given an array of $n$ numbers, checks if there is any repeated numbers in the array, and returns true if there is and false otherwise.
It uses a direct access ...
0
votes
1answer
73 views
Confusion related to dynamic programming [closed]
I was going through this dynamic programming problem. However, I have a confusion
In the third picture, having the black border, I didn't get how the
For each, we try each string of the k ...
2
votes
2answers
44 views
A* optimality of the expanded node
Suppose I have a admissible and consistent heuristic.
Is it true, that when I expand a node, I have guaranteed that the path I found to this node is optimal?
Look at this pseudocode from wikipedia:
...
6
votes
1answer
82 views
2-D peak finding complexity (MIT OCW 6.006)
In a recitation video for MIT OCW 6.006 at 43:30,
Given an $m \times n$ matrix $A$ with $m$ columns and $n$ rows, the 2-D peak finding algorithm, where a peak is any value greater than or equal to ...
10
votes
6answers
375 views
What are the characteristics of an $O(n \log n)$ time complexity algorithm?
Sometimes it's easy to identify the time complexity of an algorithm my examining it carefully. Algorithms with two nested loops of $N$ are obviously $N^2$. Algorithms that explore all the possible ...
1
vote
2answers
102 views
What is the complexity of this matrix transposition?
I'm working on some exercises regarding graph theory and complexity.
Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically ...
3
votes
2answers
119 views
Why does bubble sort do $\Theta(n^2)$ comparisons on an $n$ element list?
I have a quick question on the bubble sort algorithm. Why does it perform $\Theta(n^2)$ comparisons on an $n$ element list?
I looked at the Wikipedia page and it does not seem to tell me. I know that ...
1
vote
1answer
75 views
Confusion related to a divide and conquer problem
I have some confusion related to a divide and conquer problem. Here is the problem
You’re consulting for a small computation-intensive investment company, and they have the following type of problem ...
1
vote
1answer
26 views
Confusion related to time complexity of fast fourier transform
I have this confusion related to the time complexity of FFT. I was reading this book related to Design and Analysis of Algorithms and I came across FFT.
It says that lets say I have a polynomial of ...
2
votes
4answers
154 views
Why does a recurrence of $T(n - 1) + T(n - 2)$ yield something in $\Omega(2^{\frac{n}{2}})$?
I am trying to analyze the running time of a bad implementation of generating the $n$th member of the fibonacci sequence (which requires generating the previous 2 values from the bottom up).
Why does ...
3
votes
2answers
65 views
Algorithm to find the mode in a unimodal array
I am given the following problem in an Algorithms class:
Assume that you are given an array A[1 . . . n] of distinct numbers.
You are told that the sequence of numbers in the array is unimodal, ...
