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
8
votes
1answer
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 ...
1
vote
2answers
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 ...
6
votes
1answer
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 ...
6
votes
1answer
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 ...
4
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
2answers
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: ...
6
votes
3answers
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 ...
7
votes
2answers
74 views

Compute relational composition in $O(|E||V|)$

Definitions: Let $G=(V,E)$ be a DAG without self-loops, and $X \subseteq G$ and $Y \subseteq G$ be graphs. Input: $X,Y$. Output: The relational composition relational composition $X \circ Y$ in $\...
20
votes
3answers
20k views

Why is Radix Sort $O(n)$?

In radix sort we first sort by least significant digit then we sort by second least significant digit and so on and end up with sorted list. Now if we have list of $n$ numbers we need $\log n$ bits ...
8
votes
3answers
935 views

Finding the height of all nodes in a forest

I have a forest, i.e., nodes with directed edges and no cycles (directed or undirected). I define the height of a vertex $v$ as 0 if it does not have any incoming edges, or the maximum number of edges ...
5
votes
0answers
644 views

Arc-Length parameterization of a cubic bezier curve

I like to implement an arc-length Parameterization of a cubic bezier curve. So far I have implemented the method of calculating the arc length of the curve and now I'm stuck at calculating the times ...
3
votes
3answers
169 views

Optimize a linear recurrence

$$\begin{align*} T[1] &= 1 \\ T[2] &= 2 \\ T[i] &= T[i-1] + T[i-3] + T[i-4] & \text{for \(i \gt 2\)} \\ \end{align*}$$ I have to calculate $T[N]$, but $N$ is too big ($\approx ...
29
votes
7answers
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 ...
7
votes
2answers
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.
2
votes
2answers
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. ...
1
vote
0answers
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 ...
2
votes
2answers
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; ...
6
votes
1answer
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: ...
11
votes
2answers
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 ...
5
votes
1answer
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 ...
2
votes
1answer
2k views

Complexity of optimized bubblesort [closed]

What is the runtime complexity of the following implementation of Bubblesort (for integers)? ...
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? ...
1
vote
1answer
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 ...
6
votes
2answers
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 ...
8
votes
1answer
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 ...
0
votes
1answer
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?
2
votes
3answers
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)...
6
votes
1answer
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 ...
3
votes
1answer
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 ...
19
votes
1answer
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 ...
15
votes
2answers
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 ...
2
votes
1answer
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 ...
23
votes
1answer
3k views

Sorting as a linear program

A surprising number of problems have fairly natural reductions to linear programming (LP). See Chapter 7 of [1] for examples such as network flows, bipartite matching, zero-sum games, shortest paths, ...
10
votes
2answers
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 ...
0
votes
2answers
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 ...
4
votes
1answer
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 ...
6
votes
1answer
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, ...
5
votes
1answer
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 ...
8
votes
2answers
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 ...
5
votes
1answer
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. ...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
-2
votes
2answers
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 ...
3
votes
1answer
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 ...
12
votes
2answers
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 ...
5
votes
1answer
6k views

Finding the Shortest path in undirected weighted graph

Is there an algorithm for finding the shortest path in an undirected weighted graph?
28
votes
2answers
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 ...
4
votes
1answer
380 views

Why do the swap step in Prim's algorithm for minimum spanning trees?

I was watching the video lecture from MIT on Prim's algorithm for minimum spanning trees. Why do we need to do the swap step for proving the theorem that if we choose a set of vertices in minimum ...
5
votes
1answer
98 views

Anonymization of dataset preserving unique identities

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