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

7,540 questions
Filter by
Sorted by
Tagged with
320 views

### Problem with implementing Brzozowski's algorithm

I've been trying to implement Brzozowski's algorithm but I've just discovered that it creates suboptimal automata for a certain class of inputs, having one more state than what is really needed in the ...
2k views

### Runtime analysis of a nested loop

I have some difficulties performing the worst case analysis on this algorithm. The outermost loop is executed $2N$ times. The while loop, in the worst case, will increase by $2$ each time, so it ...
198 views

### What's a fast algorithm to decide whether there is an $A_G$ corresponding to a given $\chi_G(\lambda)$?

Given an adjacency matrix $A_G$ of an undirected graph $G$, it is easy and straightforward to compute the characteristic polynomial $\chi_G(\lambda)$. What about the other way around? The problem can ...
229 views

### Represent string as concatenations

If $S_1,S_2$ are set of strings, then $S_1S_2 = \{s_1s_2|s_1\in S_1, s_2\in S_2\}$. $S^0=\{\epsilon\}$, $\epsilon$ is the empty string. $S^n = S^{n-1}S$. Two related problems about represent string ...
162 views

### Time - Complexity Convex Optimization and Eigen Decomposition

Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be? Is the ...
225 views

### Sensor Cover Problem

We are given an interval $I$ and several points $p_1,p_2,...,p_n$. We are also given a set of sensors. Each sensor can be represented by an interval on the same line, which means all points lie within ...
86 views

### Convert table look-up into function

Two problems: Given a known table (boolean or int), convert it to a function that returns the same value using only simple operations (and, or, xor, sum...). For example: ...
5k views

### What is the difference between bounding and pruning in branch-and-bound algorithms?

Could anybody please explain what the difference between "bounding" and "pruning" in branch and bound algorithms is? I'd also appreciate references (preferably books), where this distinction is made ...
74 views

9k views

### Differences and relationships between randomized and nondeterministic algorithms?

What differences and relationships are between randomized algorithms and nondeterministic algorithms? From Wikipedia A randomized algorithm is an algorithm which employs a degree of randomness ...
5k views

### Matrix powering in $O(\log n)$ time?

Is there an algorithm to raise a matrix to the $n$th power in $O(\log n)$ time? I have been searching online, but have been unsuccessful thus far.
2k views

### How to go about working the average case run time of this trivial algorithm (and other algorithms)?

This is a similar algorithm to one I used in a previous question, but I'm trying to illustrate a different problem here. ...
759 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 ...
8k views

### Heuristic for Finding Multiple Goals in Graph - e.g. using Kruskals Algorithm

I'm a none-computer-science-student and get some knowledge on AI by taking the CS188.1x Course (Artificial Intelligence) on www.edx.org . Currently, I am working on the "Search in Pacman" Project; ...
12k views

### Finding paths with smallest maximum edge weight

I need to find the easiest cost path between two vertices of a graph. Easiest here means the path with the smallest maximum-weigth edge. In the above graph, the easiest path from 1 to 2 is: ...
3k views

### Dynamic programming with large number of subproblems

Dynamic programming with large number of subproblems. So I'm trying to solve this problem from Interview Street: Grid Walking (Score 50 points) You are situated in an $N$-dimensional grid at ...
170 views

### Meaning of the adjacency matrix product

Let $A$ be an adjacency matrix of a directed graph. What's the meaning of the $(i,j)-$entry of the matrix $((A^T)^{7} \cdot (A^{7}))$ ? My initial interpretation is that $(i,j)$ of this matrix is ...
2k views

### Complexity of optimized bubblesort [closed]

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

### Expected gain of a game of chance with differently-priced tokens

Foo and Bar are playing a game of strategy. At the start of the game, there are $N$ apples, placed in a row (in straight line). The apples are numbered from $1$ to $N$. Each apple has a particular ...
1k views

### Separate all leaves of a weighted tree with minimum weight cuts

This is part of a larger problem, which I believe I have reduced to this. Given a tree $T$ having positive edge weights, and $k$ leaves (nodes which have exactly one connected node), I need to delete ...
3k views

### Dijkstra to favor solution with smallest number of edges if several paths have same weight

You can modify any graph $G$ so that Dijkstra's finds the solution with the minimal number of edges thusly: Multiply every edge weight with a number $a$, then add $1$ to the weight to penalize each ...
1k views

### The path between any two nodes in cyclic directed graph

G{V, E} is directed, cyclic, weighted graph. What is the algorithm of finding all paths between any given two nodes? Can you suggest any good reading?
172 views

### Relation between problems and algorithms

From Wikipedia a computational problem is understood to be a task that is in principle amenable to being solved by a computer (i.e. the problem can be stated by a set of mathematical instructions)...
670 views

### An Alternative Hanoi Tower problem

We got tower $T_1$ with $n$ odd disks (1,3,5,...) and tower $T_2$ with $n$ even disks (2,4,6,...). Now we want to move all $2n$ disks to tower $T_3$. If $T(p,q)$ is a recurrence relation of minimum ...
1k views

### If I have sources and sinks of a DAG can I find the minimum number of edges to be added to make it Strongly Connected?

I am trying to create an algorithm in linear time where if given a directed acyclic graph I can add edges to make it strongly connected components. I believe I have an algorithm to identify sources ...
375 views

### Problems for which algorithms based on partition refinement run faster than in loglinear time

Partition refinement is a technique in which you start with a finite set of objects and progressively split the set. Some problems, like DFA minimization, can be solved using partition refinement ...
14k views

### Why is there the regularity condition in the master theorem?

I have been reading Introduction to Algorithms by Cormen et al. and I'm reading the statement of the Master theorem starting on page 73. In case 3 there is also a regularity condition that needs to be ...
3k views

### Using Funk SVD with SGD?

I work on a recommender system framework which is implemented with a variant on Funk SVD (See his explanation of his algorithm here). However the framework that we are trying to integrate doesn't ...
3k views

### Sorting as a linear program

A surprising number of problems have fairly natural reductions to linear programming (LP). See Chapter 7 of  for examples such as network flows, bipartite matching, zero-sum games, shortest paths, ...
4k views

### Fast k mismatch string matching algorithm

I am looking for a fast k-mismatch string matching algorithm. Given a pattern string P of length m, and a text string T of length n, I need a fast (linear time) algorithm to find all positions where P ...
97 views

### Why bound of linear function is same as that of quadratic equation

I am learning algorithms. So, I came along with something very interesting. The asymptotic bound of linear function $an+b$ is $O(n^2)$ for all $a>0$. This is same as for $an^2 + bn + c$. But ...
515 views

### Time complexity of an enumeration of SUBSET SUM instances

An instance of the SUBSET SUM problem (given $y$ and $A = \{x_1,...,x_n\}$ is there a non-empty subset of $A$ whose sum is $y$) can be represented on a one-tape Turing Machine with a list of comma ...
1k views

### Fastest square root method with exact integer result?

I am dealing with the problem of computing $s = \lfloor sqrt(x)\rfloor$ with $x \in [0,30000^2]$. The common sqrtf(x) on C language is too slow for this case, ...
415 views

### Reconstructing a data table from cross-tabulation frequencies

Say there is a data table $D$ that we cannot see, with $M$ columns. We are given exact cross-tabulation frequencies for all ${M \choose 2}$ pairs of columns, that is how often each combination of two ...
1k views

### How to find the vertices on simple path between two given vertices in a directed graph

Given a directed graph and two distinct vertices S and T, is there a polynomial-time algorithm which finds every vertex which is on at least one simple path from S to T? It is not difficult to find ...
905 views

### How to prove that BFS directed-graph traversal algorithm terminates?

How to prove that BFS directed-graph traversal algorithm terminates? (I copy the pseudocode from here) Input: A graph G and a root v of G. ...
905 views

### How to prove that the pre-order tree traversal algorithm terminates?

I see structural induction the usual way for proving an algorithm's termination property, but it's not that easy to prove by means of induction on a tree algorithm. Now I am struggling on proving that ...
2k views

### Simple Task-Assignment Problem

I have this simple 'assignment' problem: We have a set of agents $A = \{a_1, a_2, \dotso, a_n\}$ and set of tasks $T= \{t_1, t_2, \dotso, t_m\}$. Note that $m$ is not necessarily equal to $n$. Unlike ...
2k views

### complexity of decision problems vs computing functions [closed]

This is an area that admittedly I've always found subtle about CS and occasionally trips me up, and clearly others. recently on tcs.se a user asked an apparently innocuous question about N-Queens ...
164 views

### Compression of sequence with Direct Access

I have a sequence of $n$ integers in a small range $[0, k)$ and all the integers have the same frequency $f$ (so the size of the sequence is $n = f * k$). What I'm trying to do now is to compress this ...
1k views

### Minimal Spanning Tree With Double Weight Parameters

Consider a graph $G(V,E)$. Each edge $e$ has two weights $A_e$ and $B_e$. Find a spanning tree that minimizes the product $\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right)$. The ...
6k views

### Finding the Shortest path in undirected weighted graph

Is there an algorithm for finding the shortest path in an undirected weighted graph?
562 views

### How to efficiently determine whether a given ladder is valid?

At my local squash club, there is a ladder which works as follows. At the beginning of the season we construct a table with the name of each member of the club on a separate line. We then write the ...
The $k$-anonymization paradigm (and its refinements) means to create datasets where every tuple is identical with $k-1$ others. However I'm in a situation where people are in the dataset many times. ...