# 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.

754 questions
Filter by
Sorted by
Tagged with
1answer
2k views

### Complexity of optimized bubblesort [closed]

What is the runtime complexity of the following implementation of Bubblesort (for integers)? ...
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 ...
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 ...
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: ...
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 ...
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 deﬁning a hyperplane in $R^n$. Thus, tracing a path through the tree computes ...
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|$. ...
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$ ...
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?
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$,...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
1answer
45 views