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

8,529 questions
Filter by
Sorted by
Tagged with
9k views

### How to reduce the number of crossing edges in a diagram?

I am working on a diagram editor. Diagrams display 2D shapes (nodes) connected with connectors (edges). I'd like to add an operation that, given a selection of nodes, "disentangles" them: it ...
1k views

### Given an array of N integers, how can you find M elements to remove so that the array will end up in sorted order?

Here is my approach First I compute the longest non decreasing sub-sequence in $N \log N$ time. Algorithm to do this (that only uses arrays and binary search) can be found here: http://en.wikipedia....
477 views

### integer factoring using Fermat's method

Reading an article on integer factorization I implemented the following - rather inefficient - factorization method: Every odd composite can be factored as a difference of squares:  ab = \...
6k views

### Ternary Search Recurrence Relation

I am trying to work out the recurrence relation for Ternary Search. This is what I came up with: C(n) = C(n/3) + 2 However, I talked to my professor and he said ...
1k views

### Big O Notation of $n^{0.999999}\log(n)$

I'm taking the MIT Open Courseware for Introduction to Algorithms and I'm having trouble understanding the first homework problem/solution. We are supposed to compare the asymptotic complexity (big-O)...
4k views

### Running Floyd-Warshall algorithm on graph with negative cost cycle

I am trying to find the answer to the following question for the Floyd-Warshall algorithm. Suppose Floyd-Warshall algorithm is run on a directed graph G in which every edge's length is either -1, 0, ...
122 views

### What will be minimum no of operation to make whole matrix zero if one is allowed to multiply a row or column by zero?

Suppose we are given an M×N matrix, with some elements are zero, some non-zero. We know the co-ordinates of non-zero elements. Now, if I am allowed to multiply a whole row or a whole column by zero ...
364 views

### Example of an algorithm where a low-order term dominates the runtime for any practical input?

Big-O notation hides constant factors, so some $O(n)$ algorithms exist that are infeasible for any reasonable input size because the coefficient on the $n$ term is so huge. Are there any known ...
588 views

### An incrementally-condensed transitive-reduction of a DAG, with efficient reachability queries

Is there an incremental directed graph data structure that has the following properties: Keeps an internal graph structure as a DAG, and the graph is accessible (notwithstanding other helper data-...
739 views

### Number of Independent Sets in a tree

(I've been stuck on this homework assignment for far too long) I need to find the number of independent sets in a tree. For example, say the set of nodes in a tree is {A, B, C, D, E}. B and C are ...
172 views

### Estimating the time until we obtain five-in-a-row?

Consider the following random process. We have a $10\times 10$ grid. At each time step, we pick a random empty grid cell (selected uniformly at random from among all empty cells) and place a marker ...
80 views

### linklist and memory issues [closed]

I have a doubly link-list like this typedef struct Record { int i; Record* next; Record* prev; }Record; I have over 5 trillions of records that I need ...
175 views

### Drawbacks of repeating a single pattern matching procedure for many patterns

One naive approach in solving multiple pattern matching problem is to call single pattern matching procedure on each of the pattern. There must be some drawbacks in this approach, given the variety ...
679 views

### Finding both the longest and shortest path in a convex polygon

Let $S$ be a convex polygon on $n$ points. Given two points $A$ and $B$, where $A$ is left of $S$, and $B$ is right of $S$, what's an algorithm to find the shortest path from $A$ to $B$, that avoids ...
42k views

### Complexity of recursive Fibonacci algorithm

Using the following recursive Fibonacci algorithm: def fib(n): if n==0: return 0 elif n==1 return 1 return (fib(n-1)+fib(n-2)) If I input ...
737 views

### Algorithms to play randomized game

I'm interested in building an AI algorithm to play a board game. This is a sequential two-player game, where they alternate taking turns, so minimax or alpha-beta algorithms sound natural. However, ...
258 views

### N-ary (NOT binary) Gentle Boost algorithm?

I know Gentle Boost, an adaption of the AdaBoost algorithm, can be used for binary classification. However, I need to do $n$-ary classification. How do I modify or extend the GentleBoost algorithm so ...
3k views

### Algorithm for splitting array into subarrays with sums close to the target value

I have an array of positive integers, $A = (a_1, a_2, ..., a_n)$. Let $s(A)$ denote the sum of elements of array $A$. I also have an integer $t$, such that $1 < t \le s(A)$. I want to split the ...
1k views

### Iterative merge sort [closed]

I was asked to perform merge sort by iterative method. I solved it as follows: I first stored each of the elements of the array given in another array say $A$. Then I sent entries of $A$ two by two ...
1k views

### Complexity of a recursive bignum multiplication algorithm

We have started learning about analysis of recursive algorithms and I got the gist of it. However there are some questions, like the one I'm going to post, that confuse me a little. The exercise ...
290 views

### create divide and conquer algorithm

I have to create an algorithm for homework, but cant figure out where to start. The divide and conquer algorithm muse be O(nlgn) and returns a pair of numbers p and q in an array A. p must appear ...
436 views

### Complexity of keeping track of $K$ smallest integers in a stream

I need to analyze the time complexity of an online algorithm to keep track of minimum $K$ numbers from a stream of $R$ numbers. The algorithm is Suppose the $i$th number in the stream is $S_i$. Keep ...
81 views

### How to calculate Complexity Time O()? [duplicate]

Can anybody give me a way that i can use to calculate Complexity Time problems, i mean a way that will work on any complex code whatever it was. I can solve basic problems, but whenever the problem ...
1k views

### Problem with storing an existing triangulation in a DCEL

I am trying to store an existing 2D triangulation (of which I have all of the vertices and edges) in a DCEL data structure. Using the algorithm described in this answer, I was able to store a part ...
27 views

### Immediate positions algorithm?

Im studying for the computer science subject GRE test, as an exercise i need to implement the followin algorithm in java, any idea on how to aproach it?. Given a set $X$ and $z$ not in $X$, indicate ...
523 views

### Minimal size of contracting a DAG into a new DAG

We have a DAG. We have a function on the nodes $F\colon V\to \mathbb N$ (loosely speaking, we number the nodes). We would like to create a new directed graph with these rules: Only nodes with the ...