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.
9,271
questions
8
votes
1answer
7k 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
230 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
468 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 ...
18
votes
1answer
949 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 $...
20
votes
3answers
10k 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
17k 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
6k 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)$ ...
9
votes
2answers
7k 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) ...
44
votes
6answers
5k 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?
10
votes
1answer
144 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 ...
14
votes
2answers
10k 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
2k 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 ...
32
votes
6answers
63k 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
627 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
675 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 ...
asked Apr 22 '12 at 1:16
Gilles 'SO- stop being evil'
39.9k7 gold badges106 silver badges170 bronze badges
13
votes
1answer
749 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$.
...
26
votes
5answers
45k 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
1k 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
6k 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 ...
20
votes
1answer
534 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 ...
16
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
1k 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
185 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
7k 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
251 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 ...
19
votes
2answers
19k 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 ...
5
votes
1answer
2k views
Polygons generated by a set of segments
Given a set of segments, I would like to compute the set of closed polygons inside the convex hull of the set of the end of those segments. The vertices of the polygons are the intersections of the ...
8
votes
1answer
157 views
Find minimum number 1's so the matrix consist of 1 connected region of 1's
Let $M$ be a $(0, 1)$ matrix. We say two entries are neighbors if they are adjacent horizontal or vertically, and both entries are $1$'s. One wants to find minimum number of $1$'s to add, so every $1$ ...
3
votes
2answers
523 views
Survey of informed search algorithms?
I'm looking for a list of informed search algorithms, also known as heuristic search algorithms.
I'm aware of:
best-first search
Greedy best-first search
A* search
Are there more best-first ...
4
votes
3answers
1k views
How to output all longest decreasing sequences
Suppose I have an array of integers having length $N$. How can I output all longest decreasing sequences? (A subsequence consists of elements of the array that do not have to be consecustive, for ...
8
votes
1answer
234 views
Find subsequence of maximal length simultaneously satisfying two ordering constraints
We are given a set $F=\{f_1, f_2, f_3, …, f_N\}$ of $N$ Fruits. Each Fruit has price $P_i$ and vitamin content $V_i$; we associated fruit $f_i$ with the ordered pair $(P_i, V_i)$. Now we have to ...
7
votes
6answers
110k views
What is the average turnaround time?
For the following jobs:
The average wait time would be using a FCFS algorithm:
(6-6)+(7-2)+(11-5)+(17-5)+(14-1) -> 0+5+6+10+13 -> 34/5 = 7 (6.8)
What would the average turnaround time be?
7
votes
1answer
154 views
Efficient queriable data structure to represent a screen with windows on it
(this is related to my other question, see here)
Imagine a screen, with 3 windows on it:
I'd like to find an efficient data structure to represent this, while supporting these actions:
return a ...
9
votes
1answer
4k views
Chinese Postman Problem: finding best connections between odd-degree nodes
I am writing a Program, solving the Chinese Postman Problem (also known as route inspection problem) in an undirected draph and currently facing the problem to find the best additional edges to ...
10
votes
2answers
280 views
Ordering elements so that some elements don't come between others
Given an integer $n$ and set of triplets of distinct integers
$$S \subseteq \{(i, j, k) \mid 1\le i,j,k \le n, i \neq j, j \neq k, i \neq k\},$$
find an algorithm which either finds a permutation $\pi$...
14
votes
1answer
224 views
Efficiently selecting the median and elements to its left and right
Suppose we have a set $S = \{ a_1,a_2,a_3,\ldots , a_N \}$ of $N$ coders.
Each Coders has rating $R_i$ and the number of gold medals $E_i$, they had won so far.
A Software Company wants to hire ...
25
votes
1answer
5k views
Why does the splay tree rotation algorithm take into account both the parent and grandparent node?
I don't quite understand why the rotation in the splay tree data structure is taking into account not only the parent of the rating node, but also the grandparent (zig-zag and zig-zig operation). Why ...
10
votes
3answers
2k views
The space complexity of recognising Watson-Crick palindromes
I have the following algorithmic problem:
Determine the space Turing complexity of recognizing DNA strings that are Watson-Crick palindromes.
Watson-Crick palindromes are strings whose reversed ...
20
votes
2answers
2k views
How to devise an algorithm to arrange (resizable) windows on the screen to cover as much space as possible?
I would like to write a simple program that accepts a set of windows (width+height) and the screen resolution and outputs an arrangement of those windows on the screen such that the windows take the ...
7
votes
4answers
3k views
Loop invariant for an algorithm
I have developed the following pseudocode for the sum of pairs problem:
Given an array $A$ of integers and an integer $b$, return YES if there are positions $i,j$ in $A$ with $A[i] + A[j] = b$, NO ...
11
votes
4answers
357 views
Introductory books on nature sciences behind bioinformatics
My question goes to those who are concerned with computational biology algorithmics. I'm going to take a course on bioinformatics this fall; the problem, however, is that I have too little background ...
29
votes
2answers
5k views
Where to get graphs to test my search algorithms against?
I am implementing a set of path finding algorithms such as Dijkstra's, Depth First, etc.
At first I used a couple of self made graphs, but now I'd like to take the challenge a bit further and thus I'...
16
votes
3answers
15k views
dynamic programming exercise on cutting strings
I have been working on the following problem from this book.
A certain string-processing language offers a primitive operation which splits a string into two
pieces. Since this operation involves ...
