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
1answer
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 ...
3
votes
1answer
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....
6
votes
2answers
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 = \...
2
votes
2answers
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 ...
4
votes
3answers
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)...
6
votes
1answer
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, ...
2
votes
1answer
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 ...
10
votes
4answers
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 ...
4
votes
1answer
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-...
2
votes
1answer
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 ...
6
votes
1answer
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 ...
0
votes
3answers
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 ...
3
votes
2answers
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 ...
1
vote
1answer
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 ...
13
votes
4answers
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 ...
5
votes
1answer
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, ...
1
vote
0answers
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 ...
4
votes
1answer
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 ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
7
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
15
votes
3answers
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 ...
1
vote
1answer
203 views

FFT for expanded form of equation multiplication

I know how to use the FFT for multiplying two equations in $O(n\,log\,n)$ time, but is there a way to use FFT to compute the expanded equation before simplifying? For example, if you are multiplying $...
1
vote
2answers
658 views

Fundamental algorithms in formal language-automata theory [closed]

I'm willing to take a course in formal languages and automata theory , where we will explore side by side a functional programming language to implement the different algorithms we will encounter ,...
1
vote
1answer
11k views

MapReduce Pseudocode [closed]

Consider the following pseudo code for mapreduce to find the frequency of words in a collection of documents: ...
43
votes
3answers
42k views

Factorial algorithm more efficient than naive multiplication

I know how to code for factorials using both iterative and recursive (e.g. n * factorial(n-1) for e.g.). I read in a textbook (without been given any further ...
5
votes
2answers
2k views

How does Grover's Quantum Sorting avoid reading the list?

It is well known now that Grover's quantum algorithm can SORT a database of $N$ entries in $O(\sqrt{N})$ time. How can an algorithm work without reading through the list of entries which needs $O(N)$ ...
1
vote
1answer
103 views

Recover the path to a goal state in A* search algorithm

In the A* search algorithm, we use a priority queue with heuristic function to find optimum result with minimum cost. But, how do we get the path after reaching goal?
7
votes
1answer
1k views

Approximation algorithm for Feedback Arc Set

Given a directed graph $G = (V,A)$, a feedback arc set is a set of arcs whose removal leaves an acyclic graph. The problem is to find the minimum cardinality such set. I want to find out about is ...
5
votes
2answers
2k views

Find a simple path visiting all marked vertices

Let $G = (V, E)$ be a connected graph and let $M\subseteq V$. We say that a vertex $v$ is marked if $v\in M$. The problem is to find a simple path in $G$ that visits the maximum possible number of ...
1
vote
1answer
179 views

Count elements of a sorted matrix that fall into a given interval

I have a $n\times n$ matrix called $M$, and two integers $k_\min$ and $k_\max$. Each row and each column of M is sorted in the increasing order. I would like to know if there is way I can count the ...
8
votes
2answers
2k views

Simple graph canonization algorithm

I'm looking for an algorithm that provides a canonical string for a given colored graph. Ie. an algorithm that returns a string for a graph, such that two graphs get the same string if and only if ...
3
votes
2answers
3k views

Shortest Minimax Path via Floyd-Warshall

I am trying to modify the Floyd-Warshall algorithm to find all-pairs minimax paths in a graph. (That is, the shortest length paths such that the maximum edge weight along a path is minimized.) Floyd-...
3
votes
0answers
998 views

Approach to solve SPOJ Cardtrick [closed]

I am trying to solve the Problem CTRICK on SPOJ. I have an $O(n^2)$ solution that is giving “Time Limit Exceeded”. After browsing for some hints, I found that it can be solved using Interval Trees. ...
2
votes
0answers
632 views

Other greedy choices to solve activity selection problem

I have been studying about activity-selection-problem and the solution of greedy choice I came across is to select the activity that finishes in the earliest among the present activities. But surely ...
7
votes
1answer
10k views

Find all intervals that overlap with a given interval

Note: I moved this question from stackoverflow.com I have an algorithmic problem where I would like to see if it can be solved in better than $O(n)$: I have given a table $T$ of $n$ elements where ...
11
votes
2answers
3k views

Comparison between Aho-Corasick algorithm and Rabin-Karp algorithm

I am working on string searching algorithms that support multiple pattern search. I found two algorithms that seem like the strongest candidates in terms of running time, namely Aho-Corasick and ...
1
vote
1answer
361 views

Confusion regarding several time complexities including the logarithm

I am new to Advanced Algorithms and I have studied various samples on Google and StackExchange. What I understand is: We use $O(\log n)$ complexity when there is division of any $n$ number on each ...
-1
votes
1answer
214 views

Time Complexity of Algorithm

I need help with finding out the time complexity of the following algorithm: ...
3
votes
1answer
694 views

Randomized Median Element Algorithm in Mitzenmacher and Upfal: O(n) sorting step?

In the last section of chapter 3 (page 54) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the ...
2
votes
1answer
2k views

Which of the common sorting algorithms can be parallelized? [closed]

I want to know that whether which of the following algorithm can be parallelized? Bubble Sort, Insertion Sort, Selection Sort, Shell Sort, Quick Sort, Merge Sort, Radix Sort. Those which can't be, ...
6
votes
1answer
430 views

Do different variants of Mergesort have different runtime?

One of my courses introduced the following question: Given the recurrence relation for mergesort: $T(n) = 2T(n/2) + n$ How would the following parameter passing strategies influence the ...
4
votes
1answer
2k views

Finding the subset of $S$ that sums up to $k$ using a black box in $O(n)$ time

Suppose you are given an input set $S$ of $n$ numbers, and a black box that if given any sequence of real numbers and an integer $k$ instantly and correctly answers whether there is a subset of input ...
16
votes
5answers
37k views

What is the significance of negative weight edges in a graph?

I was doing dynamic programming exercises and found the Floyd-Warshall algorithm. Apparently it finds all-pairs shortest paths for a graph which can have negative weight edges, but no negative cycles. ...
1
vote
1answer
51 views

Pattern bonding problem

Let $\Sigma = {1,2,3,4}$ . We say that symbol $\sigma $ bonds with symbol $\tau$ if $\sigma = \tau$ of $\sigma = \tau +1$ for even $\sigma$ and $\sigma = \tau -1$ for odd $\sigma$ . In other ...
3
votes
1answer
10k views

Time Complexity for Creating a Graph from a File

Assume that I have a file that consists of pairs of numbers separated by a space. These numbers are the labels for vertices in my graph. For example: ...

1
149 150
151
152 153
171