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
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
143 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
741 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
223 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
396 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
774 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
9k 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) ...
43
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
119 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 ...
26
votes
6answers
56k 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
578 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
554 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
515 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
41k 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
952 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 ...
20
votes
1answer
475 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
943 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
156 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
247 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
17k 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
146 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
502 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
221 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 ...
6
votes
4answers
93k 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
139 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
248 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
202 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
4k 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
1k 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 ...