Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage.
1
vote
1answer
32 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
1answer
56 views
Graph problem, shortest path with a K
From Skiena's book,
Let G = (V,E) be a directed weighted graph such that all the weights are positive. Let v and w be two vertices in G and k ≤ |V | be an integer. Design an algorithm to find the ...
1
vote
0answers
42 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
0answers
34 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
24 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
203 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
47 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
17 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
28 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
16 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
35 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
20 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
39 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
1answer
97 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
51 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
49 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
64 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
20 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
90 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
80 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
63 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
42 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
53 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
64 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
72 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 ...
1
vote
2answers
39 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
77 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
355 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
76 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
108 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
42 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
25 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
134 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
51 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, ...
3
votes
1answer
86 views
Worst case analysis of bucket sort using insertion sort for the buckets
Suppose I am using the Bucket-Sort algorithm, and on each bucket/list I sort with insertion sort (replace nextSort with insertion sort in the wikipedia pseudocode).
In the worst case, this would ...
2
votes
1answer
61 views
Counting Inversions Using Merge Sort
In Corman, Introduction To Algorithms, 3rd edition, question 2-4 it asks to count the number of inversions in a list of numbers in $\theta( n \lg n )$ time. He uses a modified Merge Sort to ...
10
votes
0answers
115 views
How does the runtime of the Ukkonen's algorithm depend on the alphabet size?
I am concerned with the question of the asymptotic running time of the Ukkonen's algorithm, perhaps the most popular algorithm for constructing suffix trees in linear (?) time.
Here is a citation ...
2
votes
2answers
104 views
Running time of a nested loop with $\sum i \log i$ term
So I have the following pseudo-code:
Function(n):
for (i = 4 to n^2):
for (j = 5 to floor(3ilog(i))):
// Some math that executes in constant time
So ...
1
vote
1answer
33 views
Looking for non-entry level implementation of foundational algorithms and data structures in python. where to look?
I'm an autodidact who works best with a mix of theory and implementation examples. I'm having a hard time finding resources on implementing algorithms and data structures in Python (2.7-3.X ...
-1
votes
1answer
78 views
Algorithm Design Manual Question 1-7 [closed]
Skeina, The Algorithm Design Manual
Question 1-7.
Prove the correctness of the following recursive algorithm to multiply two natural numbers, for all integer constants c ≥ 2.
...
8
votes
4answers
152 views
Find the median of a list of lists
Input:
A set of $\ell$ arrays $A_i$ (of numbers).
The elements within each array are in sorted order, but the set of arrays is not necessarily sorted. The arrays are not necessarily the same size. ...
2
votes
2answers
100 views
Analyzing programs with multiple for-loops
If they were all linked to make a condition such as ($1 < i < j < k < n$), I know how to solve, but the last loop is disconnected so I have no clue on how to do these...
the ones like
...
1
vote
2answers
85 views
Finding the complexity of a recursive method
An assignment question asks me to find the complexity of a [tail] recursive algorithm, copied below. While I understand all the complexity specifics, for example that the while loop's complexity is ...
1
vote
1answer
83 views
What's the complexity of calculating the shortest path from $u$ to $v$ with Dijkstra's algorithm using binary heap?
Problem: Consider a graph $G = (V, E)$ on $n$ vertices and $m > n$ edges, $u$ and $v$ are two vertices of $G$.
What is the asymptotic complexity to calculate the shortest path from $u$ to ...
2
votes
2answers
88 views
What is meant by $\operatorname{poly}(|F|, n, e)$?
When I am reading a paper I found a notation $\operatorname{poly}( |F|,n,$$\frac{1}{\epsilon}) $.
Its not clear to me that what this notation represents. Can you please help me out?
3
votes
3answers
73 views
0
votes
1answer
71 views
Explanation of a specific recurrence with respect to Master Theorem
Concerning the Master Theorem. I have found the following equation as the base of analysis:
$\quad T(n) = aT(n/b) + \Theta(n^k)$
but I also found the following:
$\quad T(n) = aT(n/b) + ...
2
votes
1answer
52 views
The use of multiset ordering in proving termination
Based on the definition of a multiset and the information in this paper, why do we use multisets in proving the termination of a program?
Is not the well-founded order enough?
6
votes
4answers
164 views
Questions about amortised analysis
As a preperation of an exam about algorithms and complexity, I am currently solving old exercises. One concept I have already been struggling with when I encountered it for the first time is the ...
2
votes
2answers
73 views
Big-O complexity when c is a tiny fraction
Finding Big-O is pretty straightforward for an algorithm where $f(n)$ is
$$f(n) = 3n^4 + 6n^3 + 10n^2 + 5n + 4$$
The lower powers of $n$ simply fall off because in the long run $3n^4$ outpaces all ...
