Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

0
votes
0answers
12 views

Finding approximately collinear points

my issue comes from image processing. The image below is for a better understanding of the problem. I have to detect three dots (shown in black, marked with red arrows). The other points I get from my ...
1
vote
1answer
21 views

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3?

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3? (where n is a power of 3) I was told it takes: $$2(n-2) + 1 = 2n-3$$ However, I can't seem to figure out ...
-1
votes
0answers
22 views

Algorithms on Fibonacci Numbers

I want to know if there exists algorithms that: Finds if number is Fibonacci number (not using golden mean) in $O(1)$. If we use golden mean, will it be logarithmic or constant, and why? Finds ...
0
votes
0answers
14 views

Domains in Evolutionary Algorithms where solution is a set of individuals

Can someone help me find domains in field of Evolutionary Algorithms where desired solution is a set of individuals(perhaps even whole population) and not single best solution. For example i want to ...
3
votes
1answer
25 views

Understanding the flaw in a proof attempt of the Communication Complexity of Equality

I'm new to communication theory and I've been wondering where the following simple argument fails: Equality Problem We have two players, player 1 Alice who gets an $n$-bit vector $X$ and player 2 Bob ...
0
votes
1answer
52 views

k-center algorithm in one-dimensional space

I'm aware of the general k-center approximation algorithm, but my professor (this is a question from a CS class) says that in a one-dimensional space, the problem can be solved (optimal solution ...
0
votes
0answers
30 views

Optimizing Permutation Algorithm

I'm looking at Permutations Algorithm, the complexity of this algorithm is pretty high O(N*N!). The algorithm is based on this observations. GeneratePermutations("ABC")= [ABC; ACB; BAC ; BCA ; CBA ...
-1
votes
0answers
28 views

Can we tweak merge sort to perform better than quick sort? [on hold]

Generally We know Merge sort has complexity O(nlogn) and quicksort has worst case complexity of O(n^2) which rarely happens if we choose good pivot. I would like to know if there is some way to ...
0
votes
0answers
29 views

Number of all possible sequences [on hold]

If I have a list of numbers, say $L = \langle5, 10, 15, 20, 25\rangle$, how could I make a program so that I get the number of sequences for which $a_i -a_{i+1}<10$, where $a_i$ is the $i^{th}$ ...
3
votes
0answers
13 views

Detecting coplanarity by given erroneous pairwise distances

This is the question I asked four months ago and took very satisfactory answers. However, I tackle a new problem now. Here, I summarize the original problem: We have points in 3D space. We do not ...
-1
votes
0answers
22 views

Amortized cost of increment counter problem

Consider the increment-counter problem, where now the counter is represented in base 10, the initial count is 0, and where the cost of an increment is the number of digits that change. (a) Show by ...
0
votes
0answers
20 views

Booth's Algorithm Multiplication

When multiplying signed integers by Booth's algorithm, does the multiplicand always have to be negative? What happens if multiplier and multiplicand are both negative? Does the algorithm still work? ...
0
votes
1answer
28 views

Algorithm Introduction [on hold]

From what I have found out so far, Introduction to Algorithms by Cormen is the algorithm equivalent of the GOF Design Patterns book. However, can anyone recommend a more introductory book please?
-1
votes
1answer
11 views

List the edges (vertex pairs) of a minimum spanning tree for this graph in the order they would be chosen by Prim's algorithm

List the edges (vertex pairs) of a minimum spanning tree for this graph in the order they would be chosen by Prim's algorithm Please help me to understand and complete this. I would very much ...
-2
votes
0answers
14 views

How to computer the minimum operations required to perform chained matrix multiplication [on hold]

A1 x A2 x A3 x A4 Here A1 is 4x 5 , A2 is 5 x 10, A3 is 10 X 7 and A4 is 7 x 3 So far this is what i have for the matrix m [][] ) Please help me to understand and complete this problem.
4
votes
0answers
58 views

Fixed size set to contain the maximum number of given sets

I asked this question in SO here I have about 1000 sets of size <=5 containing numbers 1 to 100. {1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ... ...
3
votes
3answers
474 views

Rigorous Proof of Insertion Sort

Currently I self study CLRS book (Outside of any course, so I got no access to an instructor) And I am stuck proving Insertion Sort, The proof in CLRS book is not so formal. Here's the algorithm: ...
0
votes
0answers
18 views

Patent-free algorithm for labeling a MRF/CRF

At the moment I'm implementing a video segmentation algorithm for moved foreground / background. In the literature often a graph-cut algorithm is used, which is patented by US6973212. Are there any ...
0
votes
1answer
43 views

Proving that the average case complexity of binary search is O(log n)

I know that the both the average and worst case complexity of binary search is O(log n) and I know how to prove the worst case complexity is O(log n) using recurrence relations. But how would I go ...
0
votes
0answers
19 views

Efficient Power of Square Symmetric Matrix

It is known that computing the nth power of a matrix can be done in $O(D(n)+n \log(n))$ time, where where $D(n)$ is the time needed for diagonalization. What is known about square symmetric matrices? ...
-1
votes
0answers
24 views

An algorithm to predict petrol mileage [on hold]

I am trying to come up with a simple starter algorithm to predict petrol / gas mileage. For now I would like to keep it simple minimal factors and high accuracy is not what I am aiming for at the ...
1
vote
0answers
48 views

Prove that there always exists a fair driving schedule [on hold]

Some people agree to carpool, but they want to make sure that any carpool arrangement is fair and doesn't overload any single person with too much driving. Some scheme is required because none ...
-1
votes
1answer
30 views

Determine whether there is a valid rounding in a table of numbers

I was told this question would be better suited here: Suppose you have a table such as: $\begin{array}{ccc} 11.998 & 9.083 & 2.919 &|& 24\\ 12.983 & 10.872 & 3.145 ...
1
vote
1answer
21 views

Can there exist a recurrence relation for “sequential search”?

I'm just confused, cause from my knowledge recurrence is applied mostly to recursive procedures or divide and conquer techniques etc.
-1
votes
0answers
26 views

Deleting and querying the kth element

Given an array A containing N elements. I want to know what is best suitable data structure to handle these 2 queries : Delete Kth element from the array. Report current Kth element of the array. ...
-1
votes
0answers
18 views

Which book contain these topics from data structure [on hold]

I cannot find these topics in the books I own or have searched on google. Please guide me through this : Data structures for maintaining ranges, intervals and disjoint sets with applications. Basic ...
4
votes
1answer
58 views

Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form

As stated in the title: Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form. For example: when $p = 2$ and $q = 3$ Next of $2^2*3=12$ is ...
1
vote
0answers
55 views

Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time

Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm. For a fixed starting vertex $s$, the ...
1
vote
1answer
28 views

Find the max of a convex function in fewest samples

Suppose there is a convex function, and a certain domain interval. I want to find the max of this function within the interval. The goal is to minimize the number of times the function is evaluated, ...
-1
votes
0answers
51 views

Algorithm to determine number of strings of length n under different constraints

I am looking for an algorithm that can find the number of sequences of length $n$ that can be made from $m$ different characters $\{x_0, x_1, \cdots, x_{m-1}\}$. Several additional constraints are ...
2
votes
2answers
82 views

How do I know if my algorithm is right (without coding)? [closed]

For some background : I think I am quite good at advanced (graduate/research level) mathematics and physics but I have no CS background. Now I am taking a graduate level class on algorithms. I ...
0
votes
0answers
45 views

Is there a poly time algorithm for finding all approximate zeros contained in $[0,1]$ of a continuous poly computable $f(x)$ with at most m zeros?

Specifically we know that for our function $f$ ($f$ takes real values), $\infty>f(0)>0$, while $-\infty<f(1)<0$. So the classical binary search will find an approximate zero within ...
-1
votes
1answer
21 views

Recursion problem to see if string fits in given pattern

If you are given a pattern and a string, check recursively if the string fits in the pattern. The given pattern will be like "dooo?g*a". A question mark can be replaced with one character and asterisk ...
2
votes
0answers
5 views

Finding maximum information gain subinterval of an array containing points from 2 classes

Suppose we have an $N \times 2$ array $A$ where the two entries $A(k,1)$ and $A(k,2)$ give the number of occurrences of each of two classes at position $k$. Given a sub-interval $I$ of indices between ...
0
votes
0answers
42 views

Efficiently generating least common multiples of subsets [closed]

The non-empty subsets of $A=\{27,42,30,94\}$ are $\{27\}$, $\{42\}$, $\{30\}$, $\{94\}$, $\{27,42\}$, $\{27,30\}$, $\{27,94\}$, $\dots$, $\{27,42,94\}$, $\{42,30,94\}$, $\{27,42,30,94\}$. The LCMs ...
4
votes
0answers
65 views

Minimal covering circle

There are $n<10^4$ points on the plane. How can one approximately (with a given precision $2^{-20}$ of points' coordinates) find the minimal radius of a circle that covers some $k$ out of $n$ these ...
6
votes
9answers
250 views

What exactly is an algorithm?

I know that this may sound a bit out of the box, in fact i used to always think inside the box, but recently i've been thinking, possibly because computer science provides an high degree of freedom, ...
0
votes
1answer
54 views

To know time complexity of some code

What is the time complexity of following piece of code in terms of number of updates to S in worst case. ...
2
votes
0answers
37 views

Maze with constraint on grid [duplicate]

There are some algorithm or solving a simple maze on the web; but what I am trying to solve is a bit more complicated. Here is an example: ...
-2
votes
0answers
17 views

Minimum time intervals to fully random access an array?

Suppose that i have an array $T$ of $k$ possitions. I have a random access policy. Each array element can be accessed with equal probability $\frac{1}{k}$ at each time interval $t$. My question is how ...
0
votes
1answer
114 views

minimum spanning tree and minimum heavyweight spanning tree

a minimum heavyweight spanning tree is a spanning tree in which the heaviest edge is as light as possible. Formally, input : given connected undirected weighted graph, $G$. output : a spanning tree ...
0
votes
1answer
35 views

Creating all possible subsets and complexity calculation [duplicate]

I am a novice programmer and very weak in complexity calculation. I have learnt to write a program for creating all possible subsets from a set of elements, i.e. knapsack algorithm. Now I would like ...
0
votes
1answer
59 views

Find path to point and avoid bear

I'm so far a self taught programmer who's mostly been working on simple web and app development. But now my teacher wants me to enter a school competition in programming. Of course the competition is ...
1
vote
1answer
51 views

Given a pile of cards, how to program to get card combinations whose sum is closest to 21?

This is an interview question: Given a pile of cards, how to program to get card combinations whose sum is closest to 21? Example: input: Array : 2, 3, 4, 5, J, K output: 2, 4, 5, J 2, 4, 5, K ...
0
votes
0answers
32 views

Remove atmost K subtrees

Given a tree with N vertices numbered from 1 to N. The vertex 1 is the root of the tree. Each vertex is assigned with an integer weight. A remove operation can remove sub-tree rooted at an arbitrary ...
-1
votes
0answers
21 views

Count edges that can be removed

Given are N nodes and M edges, each edge connects two nodes. The edges are bidirectional , i.e., substance can flow in either direction through the edge. We start from node 1 and end up at node N. ...
1
vote
1answer
49 views

Order of a pseudo code

I am trying to find order of an bellow algorithm but I have no idea about, the problem like below we have an array of $n$ element name $T[1...N]$ and we have that $0\leq T[i] \leq i$ and $T[i] \in ...
6
votes
2answers
265 views

Proving NP-hardness of strange graph partition problem

I am trying to show the following problem is NP-hard. Inputs: Integer $e$, and connected, undirected graph $G=(V,E)$, a vertex-weighted graph Output: Partition of $G$, $G_p=(V,E_p)$ obtained ...
2
votes
2answers
59 views

Count points in 2-d range

You are given an array $A$ of size N $(N\leq 1\,000\,000)$ containing all integers $1..N$ exactly once. You are required to answer query in $O(\log^2 N )$ and to preprocess in $O(N\log^2N)$: How ...
4
votes
1answer
16 views

How to order objects to minimize non-adjacency cost

I have an array of $N$ objects, each appearing exactly once. I also have a list of $M$ pairs of the objects. Each pair has a "non-adjacency cost" that must be paid if the two objects are not adjacent ...