Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

Filter by
Sorted by
Tagged with
2
votes
1answer
2k views

Complexity of optimized bubblesort [closed]

What is the runtime complexity of the following implementation of Bubblesort (for integers)? ...
2
votes
1answer
200 views

Feasibility of linear inequalities with binary variables

I have a system of linear inequalities of the form $A^t x \leq b$, where each of the $x_i$'s is a binary variable in $\{0, 1\}$. Are there any known fast and practical algorithms that can find a ...
2
votes
1answer
54 views

Is there any problem that is hard to solve, can produce N equiprobable outputs and is easy to verify?

I'm looking for a problem that allows me to generate random instances which: Take arbitrary time to compute (i.e., I can generate an instance that I know would take at least 10 days to solve in an ...
2
votes
1answer
128 views

Searching for multiple partial phrases so that one original phrase can not match multiple search phrases

Given a predefined set of phrases, I'd like to perform a search based on user's query. For example, consider the following set of phrases: ...
2
votes
0answers
1k views

How are Distributed Snapshot algorithms (likes of Chandy Lamport) implemented in real world distributed systems? [closed]

Can anyone explain, how Distributed Snapshot algorithms ( Example: Chandy-Lamport are implemented in the context of modern distributed systems? Can you name an open source System implementation ...
1
vote
1answer
50 views

Help in geometrically understanding “Linear Decision Trees”

In the words of (http://www.cs.utah.edu/~suresh/5962/lectures/17.pdf, section 17.2), "Each $f(x)$ can be interpreted as defining a hyperplane in $R^n$. Thus, tracing a path through the tree computes ...
1
vote
1answer
2k views

Finding nearest of a list of points on Euclidian plane to a given reference point

Problem formulation: Given a list $L$ of $n$ points in the Euclidian plane and a reference point $R$ also in that plane, find a closest point $P\in L$ such that, for all $X\in L$, $|PR|\le|XR|$. ...
1
vote
1answer
868 views

Best way to merge 2 max heaps into a min heap

Assume we have 2 max heaps, each with n nodes. We want to merge these 2 heaps and build a min heap. What is the best way to do this? The easiest way is to consider 2 max heaps an array with $2n$ ...
1
vote
1answer
695 views

Canonical form for a graph

I am trying to find a description for canonical form (labelling) for a graph. Specifically, how do we arrive at canonical form for a given graph?
1
vote
1answer
964 views

Sort array with minimum swaps

Given an array, I need to sort the array (if not already sorted) in either decreasing or increasing order so that number of swaps are minimized. I was thinking of first determining whether it is ...
1
vote
1answer
343 views

What is the precise definition of pseudo-polynomial time (feat. Counting Sort)

From wikipedia In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required ...
1
vote
1answer
98 views

Ways to implement a decision making process involving complex rules [closed]

I'm investigating different solutions for solving what looks like a decision making problem. Although the domain I'm working on is different, for the problem at hand, it's quite easy explaining with ...
1
vote
1answer
75 views

Bit distance and disruption [duplicate]

Earlier, I asked a question defining disruption in Genetic Algorithms. Given that definition, I'm still confused on how to answer the following question. True or false? For 1-point and 2-point ...
1
vote
0answers
627 views

Knuth Yao DP Speedup - Cutting Sticks

There's a problem called Cutting Sticks - we start with one stick and n points where it needs to be cut. Cutting a stick costs the length of that stick. Of course, we want to minimize the toal cost. ...
1
vote
1answer
1k views

Solve a problem through reduction

I am aware that for a problem to be considered NP-Hard, any problem in NP must be reduceable to your problem (problem which you are trying to prove is NP-Hard). Let's assume that you have proven that ...
1
vote
2answers
868 views

Negative edge weights in Dijkstra and Bellman Ford shortest path algorithms

The main difference between Dijkstra algorithm and Bellman Ford algorithm that all texts (including CLRS) specify is that Dijkstra's algorithm need all non negative edge weights, while Bellman Ford ...
1
vote
0answers
66 views

Known algorithms: subgraph with highest/lowest diameter?

Let be $G=(V,E)$ a directed graph without self loops, where each node has an out-degree of at least $k$. We want to find a $E'\subset E$, so that $G'=(V,E')$ has the following properties: Almost all ...
1
vote
1answer
175 views

Algorithms to convert 2D videos to 3D ones

Are there published algorithms that can convert 2D videos to 3D ones? If there are few published algorithms for this I am also interested to know how the conversion quality is.
1
vote
1answer
488 views

Minimal set of rows and columns covering all non-zero entries in matrix

Given a matrix $A \in \{0,1\}^{n \times n}$, use network flows to describe an algorithm that finds the minimal set $I$ of rows and columns such that any non-zero entry is in one of the rows or columns ...
1
vote
1answer
103 views

Why the Goemans-Williamson's MAX-CUT algorithm relax the variables to vectors of $n-$dimension on unit sphere?

Why not to some constant like 3 or 4 dimension? I suspect that it is because Cholesky Decompostion will work only for $n \times n$ matrix $B$ where $B^TB = P$ where $P$ is a semidefinite matrix. Is it ...
1
vote
1answer
1k 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 ...
1
vote
1answer
1k views

How to draw a graph to disprove this statement?

The Problem: Indicate whether the following statements are true or false: a. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of at least one minimum ...
1
vote
1answer
40 views

Algorithm to extract line-like contour in 3d

Hello people on the internet, I'm currently searching for some kind of fast algorithm that allows me to extract curves in three dimensional space that arise as the intersection of two level sets of ...
1
vote
1answer
153 views

Sort binary matrix by swapping columns to make subrectangle of ones with maximum size

We have given binary matrix (matrix containing only 1 and 0) of size $n\cdot m$. We want to order the matrix such that the biggest rectangle containing only ones is with maximum size. For example if ...
1
vote
2answers
205 views

Best time complexity of sorting numbers in range [1…n log n]

given an array $A$ of $n$ numbers in range $1$ to $n\log n$, what is the time complexity of the best method to sort them? The answer is $O(n)$ but I don't understand this. of course counting sort ...
1
vote
1answer
1k views

Find a maximum matching in linear time

I need to describe an algorithm that finds a maximum matching in a given undirected and unweighted graph. The runtime needs to be linear and is a 2-approximation, that is, the matching size (number of ...
1
vote
1answer
48 views

Efficiently compute parallel matrix-vector product for block vectors?

I have $P$ processors, each having a different vector $v_p$ of size $N$, $p=1, ..., P$. I now want to compute the matrix-vector product $$w = (E\otimes I_N)v$$ in parallel, where $\otimes$ is the ...
1
vote
2answers
79 views

Find a recurrence relation for merging of sublists of an array

There are $\log n$ sublists each of size $\frac{n}{\log n}$. Write a recurrence relation for merging these lists into an $n$ element list. My Approach Let $m = \log n$. Then, $T(m) = 2T(m/2) + O(n)$,...
1
vote
3answers
270 views

Which of the following problems can be reduced to the Hamiltonian path problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks: Assume that P ≠ NP. Consider undirected graphs with nonnegative edge lengths. Which of the following problems ...
1
vote
1answer
198 views

Floyd–Warshall algorithm on an undirected graph contains negative weight edges

According to this answer, the Bellman-Ford algorithm doesn't work when an undirected graph contains negative weight edges since any edge with negative weight forms a negative cycle, and the distances ...
1
vote
2answers
2k views

Need a practical solution for creating pattern database(5-5-5) for 15-Puzzle

I have asked this exact question on StackOverflow. I did not get the answer that I was looking for. Please read this question fully before answering. Thank You. For static pattern database(5-5-5), see ...
1
vote
0answers
97 views

Why the update low value in Tarjan's for the ancestors is not it's low value instead of it's discovery value? [closed]

In Tarjan's algorithm for finding SCC/AP/Bridges, we update the value of the low[u] to be the min ( low[u], desc[v] ) given that v is a neighbor and has been discovered before, why it's not like this ...
1
vote
0answers
81 views

Conceptualizing a balance in a DFS traversal [closed]

I'm trying to use the concept of DFS traversal to go through a cycle, and attempt to get a balance of 0 in the end. Each student either owes or is owed some money, so I'm trying to go through all of ...
1
vote
2answers
373 views

Why can't we just use preorder traversal to check if a tree is subtree of binary tree?

Is preorder traversal enough to check if a tree is subtree of a binary tree? Are there any scenarios which I can miss if I use just the preorder traversal? What other methods can be used to check if ...
1
vote
1answer
114 views

Total Number of Bits Needed to Represent a List of N elements

This is an excerpt from the algorithms textbook How to Think About Algorithms by Jeff Edmonds (This book is a gem by the way). I get his conclusion about Merge/Quick/Heap sorts having $O(NlogN)$ ...
1
vote
1answer
789 views

How can you determine what set of boxes will maximize nesting?

I'm trying to find a dynamic solution to the nesting boxes problem. You're basically given a set of "boxes" which all have different dimensions. The goal is to find the maximum set of boxes that can ...
1
vote
1answer
103 views

Minimizing sum of recursive pairwise sums

What is the best algorithm for this? We are given an array of positive integers and we want to minimize the total cost of recursively adding together all the integers to one integer, two integers at ...
1
vote
1answer
99 views

Dijkstra function for navigation for disadvantaged

Is there a way we can write a function for Dijkstra to determine which node to enqueue and which to discard. This is for a navigation solution for people with disabilities where path to stairs may be ...
1
vote
0answers
756 views

Longest Increasing Subsequence

I got no responses on stackoverflow, so I'm asking here: How useful is the LIS (Longest Increasing Subsequence) problem in tackling other CS problems? There are a few algorithms, using patience ...
1
vote
1answer
170 views

How to find polygons overlap reign

I have an algorithmic problem. I have a set of different polygons in the 2D space. Each polygon is represented according to its vertex representation (x and ...
1
vote
1answer
32 views

Algorithm To Process Purchases Efficiently and Apply Constraint

I am working on a problem where I have to completely scan a large unordered log file which contains purchasing details of customers. The file structure is as follows: ...
1
vote
1answer
45 views

Checking if several sets of pairs covers a given set of pairs

Suppose we have $N$ arrays of pairs, e.g. for $N=3$: $A_1 = [ [3,2], [4,1], [5,1], [7,1], [7,2], [7,3] ]$, $A_2 = [ [3,1], [3,2], [4,1], [4,2], [4,3], [5,3], [7,2] ]$ and $A_3 = [ [4,1], [5,1], [5,...
1
vote
2answers
123 views

Working out the connectives (And, Or, Not) in a Truth Table that has the outputs [duplicate]

I don't understand how to work backwards to work out a truth table that has been filled out already (I don't know the logical operators). E.g P | Q | Output 1 | 1 | 1 1 | 0 | 0 0 | 0 | 0 0 | 1 | 0 I ...
1
vote
2answers
901 views

Community detection in weighted directed graphs for fixed number of communities

I have a weighted directed graph $G=(V,E)$ with positive weights. Say these vertices represent cities and the weight $w : V_1 \rightarrow V_2$ represents number of students moving into other cities ...
1
vote
0answers
107 views

Given a directed graph and a vertex v, find all cycles that go through v? [duplicate]

Given a set of uniquely numbered items that each has three attributes id, from and two in ...
1
vote
1answer
245 views

Maximum weighted disjoint set union

I would like to know whether the following problem is a standard problem that has been considered in the research literature. I performed some searches, which have not produced results. I call this ...
1
vote
1answer
64 views

Terminology for property of recursion definitions

I have a question about generally accepted terminology (and whether it exists at all). Some recursive algorithms on hierarchical data structures (trees) have the property that they are expressed as a ...
1
vote
1answer
152 views

Proving correctness of search algorithms

I've seen correctness proofs for other searching algorithms; however, for this particular algorithm: search in a row-wise and column wise sorted matrix, I'm not able to generate a proper proof. ...
1
vote
0answers
928 views

Divide self-intersecting polygon

I have points of self-intersecting polygon, its edges and also I am able to find points where it intersects itself using Bentley–Ottmann algorithm. I planned to build non-self intersecting polygons ...
1
vote
1answer
2k views

Interval Scheduling Problem with more than One Resource

Consider the interval scheduling problem, see also here. In order to schedule the $n$ job requests over one resource, you sort the requests in order of finish time, choose the request with earliest ...