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
32
votes
4answers
3k views

How to measure “sortedness”

I'm wondering if there is a standard way of measuring the "sortedness" of an array? Would an array which has the median number of possible inversions be considered maximally unsorted? By that I mean ...
17
votes
6answers
12k views

How is Dynamic programming different from Brute force

I was reading up on Dynamic Programming when I came across the following quote A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution. ...
14
votes
2answers
901 views

Classfication of randomized algorithms

From Wikipedia about randomized algorithms One has to distinguish between algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a ...
11
votes
1answer
1k views

Algorithm to test whether a language is regular

Is there an algorithm/systematic procedure to test whether a language is regular? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n : n \in \mathbb{N}\...
2
votes
4answers
1k views

minimum subset of dominating 2D points

From an initial set $S$ of 2D points, how to efficiently compute a minimum(-size) dominating subset $M$ ? $M$ is a dominating subset of $S$ if for any $(x,y)$ in $S$ there is at least one point (a,b) ...
4
votes
2answers
12k views

Is there an algorithm to find all the shortest paths between two nodes?

Given a directed graph, Dijkstra or Bellman-Ford can tell you the shortest path between two nodes. What if there are two (or n) paths that are shortest, is there an algorithm that will tell you all ...
4
votes
2answers
6k views

The stable marriage algorithm with asymmetric arrays

I have a question about the stable marriage algorithm, for what I know it can only be used when I have arrays with the same number of elements for building the preference and the ranking matrices. ...
4
votes
2answers
9k views

Time complexity formula of nested loops

I've just begun this stage 2 Compsci paper on algorithms, and stuff like this is not my strong point. I've come across this in my lecture slides. ...
3
votes
1answer
1k views

Dijkstra's algorithm to compute shortest paths using k edges?

I am aware of using Bellman-Ford on a graph $G=(V,E)$ with no negative cycles to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using at most $k$ ...
15
votes
1answer
16k views

Find the longest path from root to leaf in a tree

I have a tree (in the graph theory sense), such as the following example: This is a directed tree with one starting node (the root) and many ending nodes (the leaves). Each of the edge has a length ...
10
votes
2answers
3k views

Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive?

I'm currently reading introduction to algorithms and came by Johnson’s algorithm that depends on making sure that all paths are positive. the algo depends on finding a new weight function (w') that ...
9
votes
4answers
648 views

Finding the two largest of five small integers as quickly as possible

I use a variation of a 5-cross median filter on image data on a small embedded system, i.e. x x x x x The algorithm is really simple: read 5 unsigned ...
7
votes
1answer
561 views

An online algorithm to find the Pareto frontier elements

I'm looking for an online algorithm that takes a stream of elements and preserves the elements that are on the Pareto frontier (e.g. all non-dominated elements). For instance. Given the following ...
6
votes
2answers
5k views

How to find spanning tree of a graph that minimizes the maximum edge weight?

Suppose we have a graph G. How can we find a spanning tree that minimizes the maximum weight of all the edges in the tree? I am convinced that by simply finding an MST of G would suffice, but I am ...
6
votes
1answer
1k views

Does Ford-Fulkerson always produce the left-most min-cut

When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found. However, if you then use the left-over residual graph to produce a min-cut ...
4
votes
1answer
2k views

Minimum distance between start and end by going through must visit points in a maze

So, suppose i have a maze, which has a start point and an end point, marked with Orange and red respectively and my goal is to find the minimum distance between them. The blocked path is represented ...
3
votes
1answer
2k views

Efficiently enumerating all paths from i to j of given length in a graph

I've been trying to efficiently solve this problem : given a integer p > 0 and a directed graph whose nodes are 0, ..., N-1, enumerate (not simply count) all the paths (not necessarily elementary) ...
1
vote
1answer
419 views

Will this algorithm always solve a constrained sudoku puzzle in quadratic time?

Constrained Puzzle Generation: Let us say a sudoku puzzle is generated with the following procedure: Gather a sequence input of 9 unique numbers in the range $[1 .. 9]$. Call it $S$. Map $S$ to a $3 ...
51
votes
7answers
20k views

Is a Turing Machine “by definition” the most powerful machine?

I agree that a Turing Machine can do "all possible mathematical problems". But that is because it is just a machine representation of an algorithm: first do this, then do that, finally output that. ...
58
votes
8answers
4k views

Algorithmic intuition for logarithmic complexity

I believe I have a reasonable grasp of complexities like $\mathcal{O}(1)$, $\Theta(n)$ and $\Theta(n^2)$. In terms of a list, $\mathcal{O}(1)$ is a constant lookup, so it's just getting the head of ...
62
votes
3answers
11k views

In-place algorithm for interleaving an array

You are given an array of $2n$ elements $$a_1, a_2, \dots, a_n, b_1, b_2, \dots b_n$$ The task is to interleave the array, using an in-place algorithm such that the resulting array looks like $$...
35
votes
6answers
47k views

The math behind converting from any base to any base without going through base 10?

I've been looking into the math behind converting from any base to any base. This is more about confirming my results than anything. I found what seems to be my answer on mathforum.org but I'm still ...
32
votes
3answers
36k views

Algorithm that finds the number of simple paths from $s$ to $t$ in $G$

Can anyone suggest me a linear time algorithm that takes as input a directed acyclic graph $G=(V,E)$ and two vertices $s$ and $t$ and returns the number of simple paths from $s$ to $t$ in $G$. I have ...
53
votes
8answers
165k views

What is a the fastest sorting algorithm for an array of integers?

I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are: Which is the fastest ...
11
votes
3answers
2k views

Algorithm books on a range of topics

I've been tasked with building a library of books on algorithms for our small company (about 15 people). The budget is more than 5k, but certainly less than 10k, so I can buy a fair number of books. ...
17
votes
4answers
3k views

Recurrences and Generating Functions in Algorithms

Combinatorics plays an important role in computer science. We frequently utilize combinatorial methods in both analysis as well as design in algorithms. For example one method for finding a $k$-vertex ...
33
votes
2answers
10k views

Why is the log in the big-O of binary search not base 2?

I am new to understanding computer science algorithms. I understand the process of the binary search, but I am having a slight misunderstanding with its efficiency. In a size of $s = 2^n$ elements, ...
20
votes
4answers
8k views

Book for algorithms beyond Cormen

I've finished most of the material in Cormen's Intro to Algorithms book and I am looking for an algorithms book that covers material beyond Corman's book. Are there any recommendations? NOTE: I asked ...
21
votes
4answers
15k views

Least number of comparisons needed to sort (order) 5 elements

Find the least number of comparisons needed to sort (order) five elements and devise an algorithm that sorts these elements using this number of comparisons. Solution: There are 5! = 120 possible ...
11
votes
6answers
39k views

Why can't DFS be used to find shortest paths in unweighted graphs?

I understand that using DFS "as is" will not find a shortest path in an unweighted graph. But why is tweaking DFS to allow it to find shortest paths in unweighted graphs such a hopeless prospect? ...
22
votes
1answer
3k views

Complexity of taking mod

This seems like a question that should have an easy answer, but I don't have a definitive one: If I have two $n$ bit numbers $a, p$, what is the complexity of computing $a\bmod p$ ? Merely ...
12
votes
3answers
2k views

Efficient algorithm to compute the $n$th Fibonacci number

The $n$th Fibonacci number can be computed in linear time using the following recurrence: ...
13
votes
1answer
2k views

Are all MST minimum spanning trees reachable by Kruskal and Prim?

I believe this is true but have not been able to get a formal proof for either. But is it true that any minimum spanning tree is reachable by applying Kruskal's algorithm? Similarly, is this true for ...
17
votes
4answers
13k views

Maximum Independent Set of a Bipartite Graph

I'm trying to find the Maximum Independent Set of a Biparite Graph. I found the following in some notes "May 13, 1998 - University of Washington - CSE 521 - Applications of network flow": Problem: ...
9
votes
1answer
1k views

What is the most efficient algorithm and data structure for maintaining connected component information on a dynamic graph?

Say I have an undirected finite sparse graph, and need to be able to run the following queries efficiently: $IsConnected(N_1, N_2)$ - returns $T$ if there is a path between $N_1$ and $N_2$, otherwise ...
7
votes
1answer
4k views

How to find the maximum independent set of a directed graph?

I'm trying to solve this problem. Problem: Given $n$ positive integers, your task is to select a maximum number of integers so that there are no two numbers $a, b$ in which $a$ is divisible by $b$...
6
votes
1answer
3k views

Find all pairs of strings in a set with Levenshtein distance < d

I have a set of $n = $ 100 million strings of length $l = 20$, and for each string in the set, I would like to find all the other strings in the set with Levenshtein distance $\le d = 4$ from that ...
6
votes
3answers
591 views

How can I generate first n elements of the sequence 3^i * 5^j * 7^k?

How can I efficiently generate the first N elements of the sequence $3^i 5^j 7^k$, where $i,j,k \in \mathbb{N}$? I've googled around a bit and found the sequence in OEIS, but I don't really see a ...
20
votes
3answers
3k views

Is there an algorithm that provably exists although we don't know what it is?

In mathematics, there are many existence proofs that are non-constructive, so we know that a certain object exists although we don't know how to find it. I am looking for similar results in computer ...
7
votes
1answer
292 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$. ...
6
votes
2answers
451 views

Modeling the problem of finding all stable sets of an argumentation framework as SAT

As a continuation of my previous question i will try to explain my problem and how i am trying to convert my algorithm to a problem that can be expressed in a CNF form. Problem: Find all stable sets ...
4
votes
4answers
4k views

Algorithms for Connect 4?

Im designing a program to play Connect 6, a variation of connect 4. I have narrowed down my options to the following: 1) Minimax with Alpha-Beta Proning 2) A Neural Net 3) Machine Learning My ...
3
votes
2answers
118 views

Single-source shortest paths with even weight

I need help to find an algorithm that calculates the single-source shortest paths in a graph, with an extra condition that the weight of the path has to be even. In another words, we have to find the ...
3
votes
1answer
4k views

single algorithm to work on both directed and undirected graph to detect cycles?

I have been trying to implement an algorithm to detect cycles (probably how many of them) in a directed and undirected graph. That is the code should apply for both ...
2
votes
0answers
1k views

Will this address result in a cache hit or miss for these cache mapping functions?

The Problem: A CPU produces the following sequence of read addresses in hex.    Suppose the cache is empty to begin with and assuming an LRU replacement, determine whether each address ...
3
votes
1answer
337 views

Restricted version of vertex cover

I am interested in the complexity of the restricted version of the vertex cover problem below: Instance: A bipartite graph $G =(L, R, E)$ and an integer $K$. Question: Is there $S \subset L$, $...
3
votes
1answer
4k views

Minimum hamming distance of multiple binary words

Our task is to compute the minimum hamming distance for the following 16-bit words: ...
3
votes
2answers
1k views

Hamiltonian path in grid graph

Here is my situation. I have a grid-type graph with obstacles. Every move (horizontally, vertically or diagonally with a range of 1) has a cost of exactly 1 (the graph is not weighted) provided that ...
2
votes
1answer
2k views

Algorithm for solving incremental max flow problem

I am working on a project where I need to be able to compute the maximum flow between two nodes in a graph after one of the edge weights has been incremented or decremented by 1. The graph is directed ...
5
votes
2answers
12k views

$T(n)=2T(n/2)+n\log n$ and the Master theorem [duplicate]

According to Introduction to algorithms by Cormen et al, $$T(n)=2T(n/2)+n\log n$$ is not case 3 of Master Theorem. Can someone explain me why? And which case of master theorem is it?