Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

-1
votes
1answer
20 views

Why no rotate property in matrix 2d? [on hold]

Why no rotate property in matrix 2D ? we know the short hand code in matrix 2D transform:matrix(a,b,c,d,x,y) a=scale X b=Skew y c=skew X d=scale Y x=translate X y=translate Y why developers didn't ...
0
votes
0answers
8 views

Need help on implementation of MoSIFT algorithm in OpenCV [on hold]

I'm trying to do a Violence detection in a video based on the paper by Long Xu et al. "Violent video detection based on MoSIFT feature and sparse coding" and I want to know if there has been an ...
3
votes
0answers
35 views

Algorithm to optimize polling frequency between producer and consumer

I am trying to optimize what we call AJAX request polling frequency in the domain of web design. Here's a general version of the problem in simple lingo: Problem Statement: Suppose there are 3 ...
0
votes
0answers
10 views

Sigma scaling problems [migrated]

I'm developing an evolutionary genetic algorithm for which I am to use sigma scaling in order to scale the fitness evaluation of the individuals before selecting mates. Sigma scaling of fitness for ...
3
votes
1answer
50 views

Solutions to Diophantine Equations using a Min Heap

I've recently come across this problem: Find all solutions to the equation $a + 2b^2 = 3c^3 + 4d^4$ for which $a, b, c, d$ are all less than $100,000$. Hint: use one min-heap and one max-heap. ...
-4
votes
0answers
14 views

Event Planner software [on hold]

Hi all this is a program i'm working on it's an event planner software This piece of code is designed to create the actual event int createevent(char resourceslist[],char resources[], int ...
2
votes
1answer
262 views

Big O Algorithm Analysis

I'm confused about the complexity of the following code: for(i=1; i<=n; i = 2*i) for(j=1; j<=i; j++) print A[j] I know that the first loop is ...
-6
votes
0answers
21 views
1
vote
2answers
128 views

How to iterate through all values of an array?

I'm trying to implement a brute-force algorithm. If I have one variable x, I can iterate through all its values using a for ...
1
vote
1answer
29 views

Proving that an algorithm $A$ runs in $\Theta(f(n))$ time in the worst-case [duplicate]

I wanted to understand how to establish both the lower $\Omega$ and upper bound $O$ on an algorithm to conclude it runs in $\Theta$ (note that I am not trying to prove that the algorithm is the most ...
3
votes
1answer
82 views

Ford-Fulkerson Algorithm not “pushing back” flow

I am told that with every flow network, the Ford-Fulkerson algorithm produces an execution that never decreases the value of the flow on any of the edges (i.e. never “pushes back” the flow on any of ...
-1
votes
0answers
51 views

Deletion of a key edge on a flow network [on hold]

A key edge is defined to be an edge whose deletion causes the largest drop in maximum flow. I have a few questions about key edges. 1) Does a key edge always have the largest capacity of all the ...
1
vote
1answer
73 views

Prize collecting Steiner tree on graph without weights on edges

I have been trying to find an easy-to-implement approximation algorithm on the problem of Prize collecting Steiner tree on node-weighted graph without weights on the edges. The closest I have come is ...
-5
votes
0answers
26 views

Homework Tutoring (paid help) [on hold]

Looking for somebody relatively experienced in computer science to help me with some homework. Willing to pay for the service of course. If any of you are interested, drop your skype down below and we ...
0
votes
0answers
6 views

How can I arrive at an asymptotically tight upper bound and prove its correctness? [duplicate]

I am aware of Big-Oh, but often times my bounds are sloppy, which while correct is not tight enough. How can I ensure that my bound is tight? Is there a way to prove or mathematically arrive at an ...
0
votes
0answers
21 views

Maximum Sum of Substrings Algorithm

Let's consider an array of length $m$, consisting of integers, with each integer $\geq 1$. Let's also consider an arbitrary integer $1\leq n\leq \frac{m}{2}$ and two substrings (each of ...
0
votes
0answers
10 views

Finding an invalid walk order between two nodes when edges have traversal limits

Given an arbitrary connected graph with a start and goal node, with both directed and undirected edges, where each edge has a maximum number of times it may be traversed during a single traversal (at ...
1
vote
2answers
90 views

Analysis of the following integer program

So the knapsack problem has an integer programming formulation as follows, $$ \max_x v\cdot x\\s.t \\x_i \in \{0,1\}\\w\cdot x \leq C$$ Now consider the second integer program which might be a ...
0
votes
0answers
52 views

Ford–Fulkerson algorithm. Counterexamples

Consider Ford–Fulkerson algorithm (FF). Look to wiki : The following example shows the first steps of Ford–Fulkerson in a flow network with 4 nodes, source A and sink D. This example shows the ...
0
votes
1answer
26 views

Get the previous and next values of a string in lexicographic order [closed]

I'm working with a noSQL database and for certain reasons I can't use equality filtering in my queries e.g select all from database where id = 10 is NOT ...
1
vote
1answer
42 views

Using FFT to solve pattern matching problem with don't cares

I've studied about $FFT$ and it's use in string matching, but there are several issues that bother me. First I'll describe the problem and the solution I've seen in class: Suppose we have alphabet ...
3
votes
2answers
104 views

Algorithm for finding a mouse hole in a wall in O(n) time

There is this question: As a result of the US Election, a wall is built along the entire Canadian border. You have been told there is a mouse hole in the wall, but it can only be seen when you ...
0
votes
1answer
18 views

Partitioning a set to the maximum number of subsets summing to zero

Given a multiset of numbers $X = \{x_1, \dots, x_n\}$, such that $\sum X = 0$, how can $X$ be partitioned to the maximum number of subsets so that each subset sums to zero? I have searched around a ...
0
votes
1answer
47 views

How do I find the number of inversions using a red black tree?

I'm trying to figure out a way to find the number of inversions in permutation time O(nlogn) using red black trees. Here's how I think it can be done. So if I have an algorithm that inserts a new node ...
1
vote
1answer
83 views

Seating arrangement problem

$n$ professors go to a conference and have to sit together at a table. See illustration below for $n=8$ Each professor has people they like to sit next to and people they do not want to sit next ...
-3
votes
1answer
20 views

design datastructure to store an ip range(satrt and end ip and name associated with that range) and search in less than O(logn) for an ip if that ip [on hold]

design data structure to store an ip range(start and end ip and a name associated with that range) and search for an given ip address and return the name it belongs to(range name) in less than ...
-1
votes
2answers
35 views

merge sort merge phase

I'm watching a video, demonstrating merge sort, https://www.youtube.com/watch?v=EeQ8pwjQxTM At 5:42, happens something I do not understand. We are merging last 2 big arrays, ...
5
votes
1answer
50 views

String searching, where we allow characters to almost-match

Let $\Sigma= \{1,...,n\}$. Let $T$ and $Q$ be two strings with characters from the alphabet $\Sigma$ of lengths $n,k$, respectively. I am looking for an algorithm to test whether $Q$ appears as a ...
2
votes
1answer
59 views

Finding a maximal set of nonintersecting line segments in a unit circle

Let P be a set of n points that divides the unit circle into equal pieces. Let S be a set of m line segments such that their end points are points in P. The points aren't unique per line, meaning ...
1
vote
0answers
33 views

The relationship between degree of vertex and size of dominating set [closed]

I was wondering is there any relationship between degree of vertex and size of dominating set. For example, if I know the number of vertices is $n$, and I could know each vertex in the graph has ...
1
vote
0answers
28 views

Deterministic Selection Median of Medians [duplicate]

As I understand, a quick-select algorithm could use median of medians to find best suited pivot to yield the i-th item in the array, say A. I have referred to Median of Medians algorithm and steps ...
3
votes
1answer
105 views

Where can I find an original reference for this integer square root algorithm

As an exercise, I converted an old method I learned for calculating square roots on a rotary decimal hand calculator to binary. I'm sure this is not original; can anyone provide a reference? ...
-2
votes
1answer
51 views

How to design a recursive sorting given Kselect [closed]

The problem is as follows: Let A(1,...,n) be an array of distinct unsorted integers, where n is a power of 2. Your are given a linear time KSelect algorithm that you can use as a subroutine. Show how ...
1
vote
0answers
13 views

What use does the predictor stage in a particle filter have?

Im a bit confused about the particle filter. I understand the generic particle filter algorithm but in some literature say particle filter has predictor stage which is not mentioned in the generic ...
1
vote
1answer
79 views

Complexity of dynamic card game algorithm

Consider the following dynamic card game with a regular deck of 26 red cards and 26 black cards. A dealer draws the unturned cards one by one, and we can ask him to stop at any time. For every red ...
3
votes
3answers
71 views

How do I find the max and min value of an array in 3n/2−2 comparisons?

So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers ...
4
votes
1answer
191 views

Select a subset of the columns in $2\times n$ matrix, is it easy?

I want to know if this problem is polynomial-time solvable or not? The problem is: Given a nonnegative integer-valued matrix of size $2\times n$ and two nonnegative integer numbers $b<n$ and $c$. ...
0
votes
0answers
37 views

Viterbi algorithm for shortest path calculation

I have to write an essay about shortest path calculation with Viterbi algorithm. Since I am interested in finding the path with the least weight on the network graph, I am a little bit confused how to ...
4
votes
1answer
62 views

A facility location problem

Consider the following scenario. There are N localities in a town where population for locality $L_i$ is denoted by $P_i$, $i \in {1,\ldots,n}$. We need to place K hospitals around the town in a way ...
1
vote
1answer
21 views

restricted sub-permutations check

I am solving the following problem, motived by combinatorial optimization sampling proces. I have restriction (0,1) matrix to restrict which item (column index) can be on current position (row index) ...
1
vote
1answer
52 views

Match students and teachers based on ranking

I have a similar question to that of Stable Marriage Problem. This is the criteria1) 1 Student must have 1 Teacher only.2) 1 Teacher ideally should have 3-4 Students. The spreadsheet is done using ...
0
votes
0answers
40 views

How can I tell if my edge is border or interior?

I have an arbitrary collection of nodes connected by edges. I am trying to find a good way to tell if an edge/vertex is on the border or not. The red nodes and blue lines are considered on border. ...
-1
votes
1answer
39 views

Complexity and Recurrence relation for Lowest Common Ancestor Binary Tree

I have written this solution for finding the Lowest Common Ancestor in a Binary Tree. Now I wanted to find the time complexity of this problem by solving via recurrence relation. Can someone suggest ...
5
votes
1answer
52 views

Sort a list of points to form a non-self-intersecting polygon

Given a list (of arbitrary length) of 2-dimensional points, is there some algorithm that I can employ to sort this list of points into an order such that line segments sequentially drawn from $p_0 ...
-2
votes
0answers
36 views

Printing 2^n * 5^m as ascending order [duplicate]

Question: Printing 2^n * 5^m as ascending order. Answer is : 2, 4, 5, 8, 10 ... This was an interview question. and I couldn't do anything. I think we should use dynamic programming to get power ...
0
votes
1answer
45 views

Detecting all cycles in un-directed graph [duplicate]

I would like to detect all the cycles(non duplicate) in a given graph, I mean if A-B-C-A is a cycle, then A-C-B-A is a duplicate of previous one and need to be considered.I could use DFS and detect a ...
1
vote
0answers
208 views

Moving a set of points in the plane subject to constraints

I'm new to geometric algorithms and computational geometry, so please forgive me if this is an inappropriate question for this forum. Let $X$ denote the disjoint union of $n$ one-point sets. Let ...
1
vote
1answer
121 views

Efficiently locating the maximum value in interval over large amounts of data points

I have a set of $n$ two-dimensional data points $(x_i,y_i)$. I want to efficiently answer the following query: Given an arbitrary interval of $x$-values, find the highest and lowest points within ...
3
votes
2answers
111 views

Solving/Optimizing a linear system in a finite field (Z/2Z)

I'm trying to solve the following optimization problem. A is a rectangular matrix with coefficients in the finite field Z/2Z (size less than 1000 X 1000). I have a system of the form A.X = Y (X and Y ...
5
votes
3answers
139 views

Efficiently generating a uniformly random list of unique integers in a range

The problem: To generate a list of size $n$, Containing unique integers, Sampled uniformly in the range $\left[0,m\right)$, In $O(n)$ time, except that: Assuming $m$ is bounded by some word-size, ...