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.

5
votes
2answers
3k views

Find the minimal number of runs to visit every edge of a directed graph

I am looking for an algorithm to find a minimal traversal of a directed graph of the following type. Two vertices are given, a start vertex and a terminating vertex. The traversal consists of several ...
3
votes
0answers
372 views

Cyclic coordinate method: how does it differ from Hook & Jeeves and Rosenbrock?

I have trouble understanding the cyclic coordinate method. How does it differ with the Hook and Jeeves method and the Rosenbrock method? From a past exam text: Describe the cyclic coordinate ...
2
votes
2answers
1k views

Is it possible to use dynamic programming to factor numbers

Let's say I am trying to break all the numbers from 1 to N down into their prime factors. Once I have the factors from 1 to N-1, is there an algorithm to give me the factors of 1 to N using dynamic ...
18
votes
3answers
5k views

Line separates two sets of points

If there is a way to identify if two sets of points can be separated by a line? We have two sets of points $A$ and $B$ if there is a line that separates $A$ and $B$ such that all points of $A$ and ...
7
votes
1answer
2k views

Connection between KMP prefix function and string matching automaton

Let $A_P = (Q,\Sigma,\delta,0,\{m\})$ the string matching automaton for pattern $P \in \Sigma^m$, that is $Q = \{0,1,\dots,m\}$ $\delta(q,a) = \sigma_P(P_{0,q}\cdot a)$ for all $q\in Q$ and $a\in \...
74
votes
6answers
15k views

How can we assume that basic operations on numbers take constant time?

Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they run in time $O(1)$. For example, we assume this when we say that comparison-based sorting ...
21
votes
0answers
449 views

Approximate minimum-weighted tree decomposition on complete graphs

Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
6
votes
1answer
262 views

Target-Value Search (& II)

[previously appearing in cstheory, it was closed there and introduced here instead] Given an edge-weighted graph $G=(V,E)$ the problem of finding the shortest path is known to be in P ---and indeed a ...
15
votes
1answer
799 views

All soldiers should shoot at the same time

When I was a student, I saw a problem in a digital systems/logic design textbook, about N soldiers standing in a row, and want to shoot at the same time. A more difficult version of the problem was ...
7
votes
2answers
2k views

Invariant For Nested Loop in Matrix Multiplication Program

I'm making a graduate thesis about proving correctness of program for multiplying 2 matrices using Hoare logic. For doing this, I need to generate the invariant for nested loop for this program: <...
7
votes
2answers
1k views

Maximise sum of “non-overlapping” numbers in square array - help with proof

A question was posted on Stack Overflow asking for an algorithm to solve this problem: I have a matrix (call it A) which is nxn. I wish to select a subset (call it B) of points from matrix A. The ...
5
votes
3answers
3k views

Finding the maximum bandwidth along a single path in a network

I am trying to search for an algorithm that can tell me which node has the highest download (or upload) capacity given a weighted directed graph, where weights correspond to individual link bandwidths....
4
votes
1answer
575 views

Building ideal skip lists

I'm trying to find the best algorithm for converting an “ordinary” linked list into an “ideal" skip list. The definition of an “ideal skip list” is that in the first level we'll have all the ...
10
votes
2answers
1k views

How do I test if a polygon is monotone with respect to a line?

It's well known that monotone polygons play a crucial role in polygon triangulation. Definition: A polygon $P$ in the plane is called monotone with respect to a straight line $L$, if every line ...
4
votes
2answers
3k views

Running time - Linked Lists Polynomial

I have developed two algorithms and now they are asking me to find their running time. The problem is to develop a singly linked list version for manipulating polynomials. The two main operations are ...
5
votes
1answer
141 views

Techniques/tools for constructing hard instances of a puzzle game

Are there techniques and/or software tools that can be used to construct hard instances of a simple puzzle game (or a simple planning problem)? With "hard" I mean that any solution of the ...
5
votes
1answer
725 views

Approximation algorithm for TSP variant, fixed start and end anywhere but starting point + multiple visits at each vertex ALLOWED

NOTE: Due to the fact that the trip does not end at the same place it started and also the fact that every point can be visited more than once as long as I still visit all of them, this is not really ...
8
votes
1answer
6k views

Finding a worst case of heap sort

I'm working on problem H in the ACM ICPC 2004–2005 Northeastern European contest. The problem is basically to find the worst case that produces a maximal number of exchanges in the algorithm (sift ...
15
votes
3answers
1k views

How to approach Dynamic graph related problems

I asked this question at generic stackoverflow and I was directed here. It will be great if some one can explain how to approach partial or fully dynamic graph problems in general. For example: ...
7
votes
1answer
222 views

Simple paths with halt in between in directed graphs

I have two problems related to paths in a directed graph. Let $G=(V,E)$ be a directed graph with source $s \in V$ and target $t \in V$. Let $v \in V \setminus \{s,t\}$ be another vertex in $G$. Find ...
16
votes
2answers
391 views

Runtime of the optimal greedy $2$-approximation algorithm for the $k$-clustering problem

We are given a set 2-dimensional points $|P| = n$ and an integer $k$. We must find a collection of $k$ circles that enclose all the $n$ points such that the radius of the largest circle is as small as ...
16
votes
1answer
734 views

Efficiently computing or approximating the VC-dimension of a neural network

My goal is to solve the following problem, which I have described by its input and output: Input: A directed acyclic graph $G$ with $m$ nodes, $n$ sources, and $1$ sink ($m > n \geq 1$). Output: ...
7
votes
1answer
1k views

Complexity of checking whether linear equations have a positive solution

Consider a system of linear equations $Ax=0$, where $A$ is a $n\times n$ matrix with rational entries. Assume that the rank of $A$ is $<n$. What is the complexiy to check whether it has a solution $...
19
votes
3answers
8k views

What is the most efficient way to compute factorials modulo a prime?

Do you know any algorithm that calculates the factorial after modulus efficiently? For example, I want to program: ...
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 ...
7
votes
3answers
4k views

Complexity of finding the largest $m$ numbers in an array of size $n$

What follows is my algorithm for doing this in what I believe to be $O(n)$ time, and my proof for that. My professor disagrees that it runs in $O(n)$ and instead thinks that it runs in $\Omega(n^2)$ ...
8
votes
2answers
6k views

Algorithms for two and three dimensional Knapsack

I know that the 2D and 3D Knapsack problems are NPC, but is there any way to solve them in reasonable time if the instances are not very complicated? Would dynamic programming work? By 2D (3D) ...
42
votes
6answers
4k views

Dealing with intractability: NP-complete problems

Assume that I am a programmer and I have an NP-complete problem that I need to solve it. What methods are available to deal with NPC problems? Is there a survey or something similar on this topic?
9
votes
1answer
117 views

Looking for a ranking algorithm that favors newer entries

I'm working on a ranking system that will rank entries based on votes that have been cast over a period of time. I'm looking for an algorithm that will calculate a score which is kinda like an ...
15
votes
2answers
9k views

Circle Intersection with Sweep Line Algorithm

Unfortunately I am still not so strong in understanding Sweep Line Algorithm. All papers and textbooks on the topic are already read, however understanding is still far away. Just in order to make it ...
3
votes
1answer
2k views

Magic Square Check for NxN Matrix - with Minimum Complexity?

Is there any algorithm that works better than $\Theta(n^2)$ to verify whether a square matrix is a magic one? (E.g. such as sum of all the rows, cols and diagonally are equal to each other). I did ...
8
votes
1answer
6k views

How to use adversary arguments for selection and insertion sort?

I was asked to find the adversary arguments necessary for finding the lower bounds for selection and insertion sort. I could not find a reference to it anywhere. I have some doubts regarding this. I ...
10
votes
1answer
1k views

How to find contour lines for Appel's Hidden Line Removal Algorithm

For fun I am trying to make a wire-frame viewer for the DCPU-16. I understand how do do everything except how to hide the lines that are hidden in the wire frame. All of the questions here on SO all ...
25
votes
6answers
54k views

What is most efficient for GCD?

I know that Euclid’s algorithm is the best algorithm for getting the GCD (great common divisor) of a list of positive integers. But in practice you can code this algorithm in various ways. (In my case,...
8
votes
3answers
565 views

What is the name of this logistic variant of TSP?

I have a logistic problem that can be seen as a variant of $\text{TSP}$. It is so natural, I'm sure it has been studied in Operations research or something similar. Here's one way of looking at the ...
8
votes
2answers
524 views

Detecting overflow in summation

Suppose I am given an array of $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$. I want to compute the sum $S = a_1 + \ldots + a_n$ on a machine with 2's ...
13
votes
1answer
447 views

Overflow safe summation

Suppose I am given $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$ such that their sum $a_1 + a_2 + \dots + a_n = S$ also fits in a register of width $w$. ...
25
votes
5answers
38k views

When to use recursion?

When are some (relatively) basic (think first year college level CS student) instances when one would use recursion instead of just a loop?
11
votes
1answer
913 views

Distribute objects in a cube so that they have maximum distance between each other

I'm trying to use a color camera to track multiple objects in space. Each object will have a different color and in order to be able to distinguish well between each objects I'm trying to make sure ...
9
votes
1answer
5k views

Rectangle Coverage by Sweep Line

I am given an exercise unfortunately I didn't succeed by myself. There is a set of rectangles $R_{1}..R_{n}$ and a rectangle $R_{0}$. Using plane sweeping algorithm determine if $R_{0}$ is ...
19
votes
1answer
465 views

Algorithm to chase a moving target

Suppose that we have a black-box $f$ which we can query and reset. When we reset $f$, the state $f_S$ of $f$ is set to an element chosen uniformly at random from the set $$\{0, 1, ..., n - 1\}$$ where ...
10
votes
1answer
2k views

Lower bound for finding kth smallest element using adversary arguments

In many texts a lower bound for finding $k$th smallest element is derived making use of arguments using medians. How can I find one using an adversary argument? Wikipedia says that tournament ...
15
votes
4answers
10k views

Quicksort explained to kids

Last year, I was reading a fantastic paper on “Quantum Mechanics for Kindergarden”. It was not easy paper. Now, I wonder how to explain quicksort in the simplest words possible. How can I prove (or ...
6
votes
3answers
8k views

Quicksort vs. insertion sort on linked list: performance

I have written a program to sort Linked Lists and I noticed that my insertion sort works much better than my quicksort algorithm. Does anyone have any idea why this is? Insertion sort has a ...
5
votes
1answer
881 views

Optimizing a strictly monotone function

I am looking for algorithms to optimize a strictly monotonic function $f$ such that $f(x) < y$ $f : [a,b] \longrightarrow [c,d] \qquad \text{where } [a,b] \subset {\mathbb N}, [c,d] \subset {\...
11
votes
1answer
153 views

Sharp concentration for selection via random partitioning?

The usual simple algorithm for finding the median element in an array $A$ of $n$ numbers is: Sample $n^{3/4}$ elements from $A$ with replacement into $B$ Sort $B$ and find the rank $|B|\pm \sqrt{n}$ ...
1
vote
4answers
2k views

Extending the implementation of a Queue using a circular array

I'm doing some exam (Java-based algorithmics) revision and have been given the question: Describe how you might extend your implementation [of a queue using a circular array] to support the ...
14
votes
1answer
6k views

Randomized Selection

The randomized selection algorithm is the following: Input: An array $A$ of $n$ (distinct, for simplicity) numbers and a number $k\in [n]$ Output: The the "rank $k$ element" of $A$ (i.e., the one in ...
4
votes
1answer
246 views

Modified Djikstra's algorithm

So, I'm trying to conceptualize something: Say we have a weighed graph of size N. A and B are nodes on the graph. You want to find the shortest path from A to B, given a few caveats: movements on ...
18
votes
2answers
16k views

Shortest Path on an Undirected Graph?

So I thought this (though somewhat basic) question belonged here: Say I have a graph of size 100 nodes arrayed in a 10x10 pattern (think chessboard). The graph is undirected, and unweighted. Moving ...