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
2k views

Complexity of optimized bubblesort [closed]

What is the runtime complexity of the following implementation of Bubblesort (for integers)? ...
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 ...
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 ...
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: ...
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 ...
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 ...
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|$. ...
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$ ...
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?
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$,...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$ ...
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 ...
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 ...
99 views

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